首页 > 代码库 > 石子合并【环形DP】

石子合并【环形DP】

2024-09-23 15:01:57   217人阅读

先放上luogu的石子合并题目链接

这是一道环形DP题，思想和能量项链很像，在预处理过程中的手法跟乘积最大相像。

用一个m[][]数组来存储石子数量，m[i][j]表示从第 i 堆石子到第 j 堆石子的总数。

接下来三重循环

　　i 表示合并操作的起始位置， j 表示合并操作的终点，也就是把 i 到 j 合并

　　k表示间断点，即 i 到 j 合并过程中选择k点来作为合并位置 

　　状态转移方程

　　f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+m[i][k]+m[k+1][j]);
　　d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+m[i][k]+m[k+1][j]);

　　注意该题有一个拆环为链的思想，设从1到n的石子数为12345

　　实际存到数组里的就是123451234

　　这样化成链就可以避免复杂的取余  毕竟作者循环队列学的不好，用一个环做的话一会就搞晕了

　　最后贴代码

　　

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int q[1000];
 5 int m[300][300];
 6 int f[300][300];
 7 int d[300][300];
 8 int main(){
 9     //memset(d,127/3,sizeof(d));
10     int n;
11     cin>>n;
12     for(int i=1;i<=n;++i){
13         cin>>q[i];
14         q[i+n]=q[i];
15     }
16     m[1][1]=q[1];
17     for(int i=1;i<=n*2-1;++i)    m[1][i]=m[1][i-1]+q[i];
18     for(int i=1;i<=n*2-1;++i)
19         for(int j=i;j<=n*2-1;++j)
20             m[i][j]=m[1][j]-m[1][i-1];
21     for(int i=n*2-1;i>=1;--i)
22         for(int j=i+1;j<=i+n&&j<n*2;++j){
23             d[i][j]=0x7fffffff;
24             for(int k=i;k<j;++k){
25                 f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+m[i][k]+m[k+1][j]);
26                 d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+m[i][k]+m[k+1][j]);
27             }
28         }
29     int maxx=0,minn=0x7fffffff;
30     for(int i=1;i<=n;++i){
31         minn=min(minn,d[i][i+n-1]);
32         maxx=max(maxx,f[i][i+n-1]);
33     }
34     cout<<minn<<endl<<maxx;
35     return 0;
36 }

 

石子合并【环形DP】


联系
我们