资深守护
7个WA,6个TLE
孙志浩在2018-11-05 20:11:46追加了内容
请在答案中解释每个变量的含义，要思路。
孙志浩在2018-11-07 20:39:52追加了内容
答案中的数组要写出含义，要思路，思路，思路！
孙志浩在2018-12-20 20:27:17追加了内容
还有，我发现，2957跟3089好像是相同的？？？
孙志浩在2019-01-05 10:08:44追加了内容
附上9分代码：
#include <iostream>
#include <vector>
using namespace std;
#define pb push_back
#define r b[i]
vector<int>f[52];
int n,k,p,i,u[200008],b[200008],w,j;
long long ans;
int main()
{
cin>>n>>k>>p;
for(i=1;i<=k;++i)f[i].pb(0);
for(i=1;i<=n;++i)
{
cin>>b[i]>>w;
f[b[i]].pb(i);
if(w<=p)u[i]=u[i-1]+1;
else u[i]=u[i-1];
}
for(i=1;i<=n;++i)
{
for(j=f[r].size()-1;j>=1;--j)
{
if(f[r][j]<=i)break;
if(u[f[r][j]]>u[i])ans++;
}
}
cout<<ans;
return 0;
}y
新手守护
我会我会！！！
Look at 思路：
设f[i]为第1~i的客栈中编号最大的最低消费不大于p的编号,r[i]为第1~i-1的客栈中
编号最大的色调与i客栈相同的编号,c1[i]=1~i-1号旅馆中与第i号旅馆色调相同的
客栈数目,c2[i]=1~i-1号客栈中与第i号客栈色调相同,且到第i号旅馆路上存在最低消费不大于p的客栈的客栈数
目,输出答案为Σc2[i],i∈(1,n]
(1)若f[i]<r[i],则1~r[i]号客栈中编号最大的最低消费小于p的客栈编号与1~i的相同,
即f[i]=f[r[i]],c2[i]=c2[r[i]]
(2)若f[i]>=r[i],则1~r[i]路上,所有与i号客栈颜色相同的客栈到i号客栈路上必
然存在一个旅馆的最低消费不大于p,
c2[i]=c1[i]
color[i]=之前所有客栈中，色调为i的客栈个数,maxc[i]=之前所有客栈中，色调为i的最大编号
许天奕在2019-01-22 10:53:39追加了内容
主要循环部分如下：
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
r[i]=maxc[a];
if(b<=p) f[i]=i;
else f[i]=f[i-1];
c1[i]=color[a];
if(f[i]<r[i]) c2[i]=c2[r[i]];
else c2[i]=c1[i];
maxc[a]=i;
color[a]++;
}
最后是定义和处理循环了，自己想吧，bye！！
资深守护
eee
修练者
1
初级天翼
孙志浩 ，这可是个4分题，有难度哦。
不知道你学到哪里了，但是这题确实难，但我可以告诉你点核心。
第一，你要注意这个：
其次需要注意留一个变量存放方案数。
修练者
不会
高级天翼
1
