首页 > 代码库 > NYOJ 737 石子合并（一）

NYOJ 737 石子合并（一）

2024-07-13 23:15:35   225人阅读

分析：

本题为区间型动态规划，dp[i][j] 表示从第 i 堆合并到第 j 堆的最小代价，

sum[i][i] 表示第 i 堆到第 j 堆的石子总和，则动态转移方程：

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j])  (i <= k <= j - 1)。

代码如下：

 1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 const int maxn = 200 + 5; 6 const int INF = 1000000000; 7 int dp[maxn][maxn], sum[maxn][maxn], stone[maxn]; 8 int main() 9 {10     int n;11     int i, j, k;12     while(~scanf("%d", &n))13     {14         for(i = 1; i <= n; i ++)15             scanf("%d", &stone[i]);16         for(i = 1; i <= n; i ++)17         {18             dp[i][i] = 0;    //不合并，代价为019             sum[i][i] = stone[i];20             for(j = i + 1; j <= n; j ++)21                 sum[i][j] = sum[i][j - 1] + stone[j];22         }23         for(int dui = 2; dui <= n; dui ++)  //合并石子的堆数24         {25             for(i = 1; i <= n - dui + 1; i ++)  //从第 i 堆到第 j 堆26             {27                 j = dui + i - 1;28                 dp[i][j] = INF;29                 for(k = i; k <= j - 1; k ++)30                     dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);31             }32         }33         printf("%d\n", dp[1][n]);34     }35     return 0;36 }
View Code


联系
我们