首页 > 代码库 > TYVJ1088

TYVJ1088

2024-07-19 06:50:35   218人阅读

区间DP
设状态dp[i][j]表示左边取i个右边取j个所能得到的最大值
dp[i][j]只可能由两个状态得到:由dp[i-1][j]再取左边一个或者由dp[i][j-1]再取右边一个则状态方程有了：
dp[i][j] = max(dp[i-1][j]+r*a[i],dp[i][j-1]+r*a[n-j+1])
r是区间半径，即此刻要左边取的+右边取的==r i+j=r；
初始化dp[0][j]和dp[i][0]这个没什么好说的。。。。
最后遍历一遍dp中i+j==n的值取出最大值即为ans
感想：
dp真是让人无奈，无力，这特么跟本想不到的东西，就让人家说的非常简单。。。。。唉，向着dp 200题继续刷吧

 

 

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 2005; 7 int dp[maxn][maxn],a[maxn]; 8 int main() 9 {10     //freopen("in.txt","r",stdin);11     int n;12     while(cin>>n)13     {14         for(int i = 1;i<=n;++i)15             scanf("%d",a+i);16         dp[0][0] = 0;17         for(int i = 1;i<=n;++i)18         {19             dp[i][0] = dp[i-1][0]+i*a[i];20             dp[0][i] = dp[0][i-1]+i*a[n-i+1];21         }22         for(int r = 2;r<=n;++r)23             for(int i = 1;i<r;++i)24             {25                 int j = r-i;26                 dp[i][j] = max(dp[i-1][j]+r*a[i],dp[i][j-1]+r*a[n-j+1]);27             }28         int ans = -1;29         for(int i = 0;i<=n;++i)30             ans = max(ans,dp[i][n-i]);31         printf("%d\n",ans);32     }33     return 0;34 }

 

TYVJ1088


联系
我们