题意：玩n次剪刀石头布,对方每次出什么已经知道了.你出的招数必须是连续的几段(不能超过k+1段),问你最多赢几次.(n<=100000,k<=20)
正常做法:f[i][j][k]表示前i次，分j段,最后一次出的是k(k=0,1,2)时最多赢几次,可以O(nk)解决,转移时看最近一次有没有新分一段即可.
智障做法:我们同样定义f[i][j][k]表示前i次,分j段,最后一次出的是k时最多赢几次,但转移的时候考虑最近的一段,也就是枚举最近的一段是从哪里开始的，那么这就变成了1D1D动态规划,打表观察到决策单调性,可以大力写一个决策单调性O(nlognk)解决,强行多一个log也可以过
讲道理决策单调性还是很好写的
#include<cstdio> #include<algorithm> using namespace std; const int maxn=100005; int sum[3][maxn]; int f[22][maxn][3]; void solve(int l,int r,int L,int R,int j,int t){//printf("%d %d %d %d %d ",l,r,L,R,j); if(l>r)return; int mid=(l+r)>>1,g=0,tmp=0; for(int i=L;i<=R&&i<=mid;++i){ tmp=sum[t][mid]-sum[t][i]; for(int k=0;k<3;++k) if(tmp+f[j-1][i][k]>f[j][mid][t]){ f[j][mid][t]=f[j-1][i][k]+tmp;g=i; } } solve(l,mid-1,L,g,j,t);solve(mid+1,r,g,R,j,t); } int main(){ int n,k; scanf("%d%d",&n,&k);k++; char buf[3]; for(int i=1;i<=n;++i){ scanf("%s",buf); for(int k=0;k<3;++k)sum[k][i]=sum[k][i-1]; if(buf[0]=='H')sum[0][i]++; else if(buf[0]=='S')sum[1][i]++; else sum[2][i]++; } for(int j=1;j<=k;++j){ for(int t=0;t<3;++t)solve(1,n,0,n-1,j,t); }//printf("%d ",f[1][4]); int ans=0; for(int i=1;i<=k;++i)for(int t=0;t<3;++t)ans=max(ans,f[i][n][t]); printf("%d ",ans); return 0; }