嗯这道题我的做法是典型的用空间换时间
用a[i][j]记录颜色为i的客栈出现的坐标，每次枚举当前客栈到前一个同颜色的客栈间是否有符合条件的客栈，如果有，就是当前客栈之前出现的所有同色客栈数量，如果没有，就是上一个同色客栈的答案数，最后从头到尾遍历一遍每个客栈的答案累加，输出，结束
但是就在我写这篇博客的时候，我突然意识到，对于a数组，当当前节点为j时，我最多只用到了同色的客栈数以及a[i][j-1]，那不就可以优化一维只记录上次同色客栈的答案数么？？？？？？？那不就不用用空间换时间了？？？？？
md我真是个智障。。
附上我无脑开的不知道浪费了多少空间的代码。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<stack> 7 #include<deque> 8 #include<algorithm> 9 #define ll long long 10 using namespace std; 11 const ll oo=0x3f3f3f3f; 12 const ll N=200005; 13 const ll M=55; 14 15 ll n,k,p,sum; 16 ll ans[N],a[M][N],b[N]; 17 18 ll Min(ll a,ll b){return a<b?a:b;} 19 ll Max(ll a,ll b){return a>b?a:b;} 20 ll Abs(ll a){return a>0?a:-a;} 21 22 ll get(){ 23 char zy=getchar(); 24 ll z=1,y=0; 25 while(zy>‘9‘||zy<‘0‘){ 26 if(zy==‘-‘) z=-1; 27 zy=getchar(); 28 } 29 while(zy>=‘0‘&&zy<=‘9‘){ 30 y=(y<<1)+(y<<3)+zy-‘0‘; 31 zy=getchar(); 32 } 33 return z*y; 34 } 35 36 int main(){ 37 //freopen("P1311选择客栈.in","r",stdin); 38 //freopen("P1311选择客栈.out","w",stdout); 39 n=get();k=get();p=get(); 40 for(ll i=1;i<=n;i++){ 41 bool ok=false; 42 ll c=get();b[i]=get(); 43 if(a[c][0]){ 44 for(ll j=a[c][a[c][0]];j<=i;j++){ 45 if(b[j]<=p){ 46 ok=true; 47 break; 48 } 49 } 50 if(ok) ans[i]=a[c][0]; 51 else ans[i]=ans[a[c][a[c][0]]]; 52 } 53 a[c][++a[c][0]]=i; 54 } 55 for(ll i=1;i<=n;i++) sum+=ans[i]; 56 printf("%lld\n",sum); 57 return 0; 58 }
原文：https://www.cnblogs.com/hahaha2124652975/p/11644870.html