首页 > 代码库 > TYVJ1062

TYVJ1062

2024-07-19 06:51:19   219人阅读

和1055沙子合并类似
环形石子合并，还是区间DP
这里需要求两个，一个是最小总代价，一个是最大总代价，两个只需要把min和max改一下其他一模一样。
以最小代价为例：
dp[i][j]表示合并从i到j的石子所需要的最小总代价，这里和线段石子合并不同的是，可以循环，说白了就是j可以大于n，这种环形的东西，一直让我感到很麻烦，但也没能想出很好的办法，所以就分两种情况判断了一下，就j<=n和j>n，前者和之前一样没有任何区别，后者for(int k = i;k<j;++k)这里可以直接循环，在循环体内的时候j和k要 %n。。我曾尝试把前面那两个对j的判断合并，但是由于j%n==0一直不知道这里怎么办，后来就放弃了。
仔细想一下，自己举两个例子再把大脑当成CPU手动运行一下就很好理解了。。。最后求得的dp[i][j]中取区间为n（即dp[1][n]、dp[2][1]、dp[3][2]、dp[4][3]....dp[n][n-1]）当中的最小值。
其实只要理解了直线型的石子合并，这题主要的想法就已经不在DP上了。

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #define INF 11111111 6 #define maxn 105 7 using namespace std; 8 int dp[maxn][maxn],d[maxn][maxn],sum[maxn]; 9 int main()10 {11     int n,m;12     while(cin>>n>>m)13     {14         sum[0] = 0;15         for(int i = 1;i<=n;++i)16         {17             int t;18             scanf("%d",&t);19             sum[i] = sum[i-1]+t;20         }21         for(int i = 1;i<=n;++i)22             for(int j = 1;j<=n;++j)23             {24                 dp[i][j]=(i==j?0:INF);25                 d[i][j]=(i==j?0:-1);26             }27         for(int r = 2;r<=n;++r)28             for(int i = 1;i<=n;++i)29             {30                 int j = i+r-1;31                 if(j<=n)32                 {33                     for(int k = i;k<j;++k)34                     {35                         dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]);36                         d[i][j] = max(d[i][j],d[i][k]+d[k+1][j]);37                     }38                     dp[i][j]+=(sum[j]-sum[i-1]);39                     d[i][j]+=(sum[j]-sum[i-1]);40                 }41                 else42                 {43                     for(int k = i;k<=j;++k)44                     {45                         dp[i][j%n] = min(dp[i][j%n],dp[i][k%n]+dp[(k+1)%n][j%n]);46                         d[i][j%n] = max(d[i][j%n],d[i][k%n]+d[(k+1)%n][j%n]);47                     }48                     dp[i][j]+=(sum[n]+sum[j]-sum[i-1]);49                     d[i][j]+=(sum[n]+sum[j]-sum[i-1]);50                 }51             }52         int mmin = dp[1][n];53         int mmax = d[1][n];54 55         for(int i = 2;i<=n;++i)56         {57             mmin = min(mmin,dp[i][(i+n-1)%n]);58             mmax = max(mmax,d[i][(i+n-1)%n]);59         }60         if(m>mmax)printf("It is easy\n");61         else if(m<mmin)printf("I am..Sha...X\n");62         else printf("I will go to play WarIII\n");63     }64     return 0;65 }

 

TYVJ1062


联系
我们