Luogu3736 https://www.luogu.org/problemnew/show/P3736
很容易想到直接 DP, 关键是枚举顺序.
\(1.\) 设后一段构成最后一个点, 前一段构成前面的点, 那么能得到 \(1\) 个点的数量要求 : \(1,k,2k-1...\) 相差 \(k-1\)
\(2.\) 注意循环的正逆顺序 : \(mid\) 比 \(j\) 小 , 正序枚举 \(j\) ; \(mid\) 比 \(i\) 大 , 倒序枚举 \(i\)
具体细节见代码
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define debug(...) fprintf(stderr,__VA_ARGS__)
- #define Debug(x) cout<<#x<<"="<<x<<endl
- #define int long long
- using namespace std;
- typedef long long LL;
- const int INF=1e9+7;
- inline LL read(){
- register LL x=0,f=1;register char c=getchar();
- while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
- while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
- return f*x;
- }
- int f[305][305][305],g[2],c[305],w[305],a[305];
- int n,K,ans=-INF;
- signed main(){
- n=read(),K=read();
- for(int i=1;i<=n;i++) a[i]=read();
- for(int i=0;i<(1<<K);i++) c[i]=read(),w[i]=read();
- for(int i=1;i<=n;i++){
- for(int j=i;j<=n;j++)
- for(int k=0;k<(1<<K);k++)
- f[i][j][k]=-INF;
- }
- for(int i=n;i>=1;i--)
- for(int j=i;j<=n;j++){
- // 注意循环的正逆顺序: mid 比 j 小, 正序枚举 j;mid 比 i 大, 倒序枚举 i
- if(i==j){f[i][j][a[i]]=0;continue;}
- int len=j-i;
- len%=K-1; if(!len) len=K-1;// 最终能剩下 len 个
- for(int mid=j;mid>i;mid-=K-1){
- for(int op=0;op<(1<<len);op++){
- f[i][j][op<<1]=max(f[i][j][op<<1],f[i][mid-1][op]+f[mid][j][0]);// 直接转移
- f[i][j][op<<1|1]=max(f[i][j][op<<1|1],f[i][mid-1][op]+f[mid][j][1]);
- }
- }
- if(len==K-1){
- g[0]=g[1]=-INF;
- for(int op=0;op<(1<<K);op++)
- g[c[op]]=max(g[c[op]],f[i][j][op]+w[op]);// 加上操作一次的分数
- f[i][j][0]=g[0],f[i][j][1]=g[1];// 用临时数组更新
- }
- }
- for(int op=0;op<(1<<K);op++)
- ans=max(ans,f[1][n][op]);
- printf("%lld\n",ans);
- }
[HAOI2016] 字符合并
来源: http://www.bubuko.com/infodetail-3050335.html