[JZOJ P1291] [DP]添加括号

@kaike

传送门

区间DP弄得我一脸懵

动态方程为f[i][j]=f[i][k]+f[k+1][j]+sum[i][j];

这题要求出最小中间和，并且要输出方案
先预留出所有的中间和
设出一个最小值，记录断点所在的位置
用con[i][j]就表示从第i个到第j个中第一个括号的位置
输出：
其中f[1][n]就是从1到n中间和
用递推的方式输出con[1][n]的 1 void cout1(int i,int j)

2 { 3 if(i>=j) 4 { 5 cout<<a[i]; return; 6 }//括号在数之前，已经输出括号，现在来输出数字 7 cout<<"("; cout1(i,con[i][j]);//输出左括号，再从i到这个括号中间找括号 8 cout<<"+"; cout1(con[i][j]+1,j);//输出 +，证明这个括号之前的数都已经输出完毕，往后递推 9 cout<<")"; 10 } 11 void cout2(int i,int j) 12 { 13 if(i>=j) return ; 14 cout2(i,con[i][j]); 15 cout2(con[i][j]+1,j); 16 cout<<sum[j]-sum[i-1]<<' '; 17 }

 

1 #include<iostream> 2 using namespace std; 3 long f[51][50001]; 4 int q1[51]; 5 int q2[51]; 6 int main() 7 { 8 int k,v,n; 9 int value,weight; 10 cin>>k>>v>>n; 11 for(int i=0;i<=k;i++) 12 for(int j=0;j<=v;j++) 13 f[i][j]=-99999999;//赋初值 14 f[1][0]=0;//当背包容量为0时，赋值0 15 for(int i=1;i<=n;i++)//枚举背包 16 { 17 cin>>weight>>value; 18 for(int j=v;j>=weight;j--)//枚举容量 19 { 20 for(int w=1;w<=k;w++)//枚举k包 从1-k 21 { 22 q1[w]=f[w][j]; 23 q2[w]=f[w][j-weight]+value; 24 } 25 int h1=1,h2=1,h=0; 26 while(h<k) 27 { 28 h++; 29 if(q1[h1]>q2[h2]) { 30 f[h][j]=q1[h1]; 31 h1++; 32 } 33 else { 34 f[h][j]=q2[h2]; 35 h2++; 36 } 37 } 38 } 39 } 40 int ans=0; 41 for(int i=1;i<=k;i++) 42 ans+=f[i][v]; 43 cout<<ans<<endl; 44 return 0; 45 } 蠢哭

 

转载于:https://www.cnblogs.com/Kaike/p/6007334.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的[JZOJ P1291] [DP]添加括号的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。