TYVJ1014

水题,凑数。
区间DP
设dp[i][j]表示从取完i到j所能得到的最小分数
枚举区间半径 r(最大为n-2)
枚举起点i,同时可以得到j
转移方程去看代码
DP目标dp[2][n-2];

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

TYVJ1014的相关文章

tyvj1014 乘法游戏

描述 乘法游戏是在一行牌上进行的.每一张牌包括了一个正整数.在每一个移动中,玩家拿出一张牌,得分是用它的数字乘以它左边和右边的数,所以不允许拿第1张和最后1张牌.最后一次移动后,这里只剩下两张牌.    你的目标是使得分的和最小.    例如,如果数是10 1 50 20 5,依次拿1.20.50,总分是                       10*1*50+50*20*5+10*50*5=8000    而拿50.20.1,总分是1*50*20+1*20*5+10*1*5=1150. 输