首页 > 代码库 > TYVJ1056

TYVJ1056

2024-07-19 06:54:33   212人阅读

和环形石子合并一个德行的一道题，区间DP
唯一的区别在于计分方式，转移方程也有所不同
dp[i][j]表示合并i到j和能得到的最大的能量
dp[i][j] = max{f[i]*r[k]*r[j]+dp[i][k]+dp[k+1][j]|i<=k<j}
还有就是因为是环形的，所以当每次循环到n时就需要特殊处理了，数学功底不行，所以只能用笨法来一点一点处理了
dp目标dp[i][i-1]中的最大值
(dp[i][i-1]由来，dp[i][(i+n-1)%n]==dp[i][i-1])

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6  7 const int maxn = 105; 8 int f[maxn],r[maxn],dp[maxn][maxn]; 9 int main()10 {11     //freopen("in.txt","r",stdin);12     int n;13     cin>>n;14     int t;15     cin>>t;16     f[1]=t;17     for(int i = 2;i<=n;++i)18     {19         cin>>t;20         r[i-1] = t;21         f[i] = t;22     }23     r[n] = f[1];24     memset(dp,0,sizeof(dp));25     for(int s = 2;s<=n;++s)26     {27         for(int i = 1;i<=n;++i)28         {29             int j = s+i-1;30             if(j<=n)for(int k = i;k<j;++k)31                 dp[i][j]=max(dp[i][j],f[i]*r[k]*r[j] + dp[i][k] + dp[k+1][j]);32             else33                 for(int k = i;k<j;++k)34                 {35                     if(k<n)dp[i][j-n]=max(dp[i][j-n],f[i]*r[k]*r[j-n]+dp[i][k]+dp[k+1][j-n]);36                     else if(k==n)dp[i][j-n]=max(dp[i][j-n],f[i]*r[k]*r[j-n]+dp[i][k]+dp[1][j-n]);37                     else dp[i][j-n]=max(dp[i][j-n],f[i]*r[k-n]*r[j-n]+dp[i][k-n]+dp[k+1-n][j-n]);38                 }39         }40     }41     int ans = dp[1][n];42     for(int i = 2;i<=n;++i)43         ans=max(ans,dp[i][i-1]);44     printf("%d\n",ans);45     return 0;46 }

 

TYVJ1056


联系
我们