nyoj 737 石子合并（一）。区间dp-白红宇

nyoj 737 石子合并（一）。区间dp

阅读量：5020 次

发布时间：2019-06-12

本文共 3196 字，大约阅读时间需要 10 分钟。

数据很小，适合区间dp的入门

对于第[i, j]堆，无论你怎么合并，无论你先选哪两堆结合，当你把[i, j]合成一堆的那一步的时候，花费肯定就是sum[i....j]

可以用纸模拟下。

那么我们设dp[i][j]表示把i...j堆合成一堆的时候的最小花费。

比如dp[1][1] = 0。dp[1][2] = a[1] + a[2];

那么要求dp[i][j]，则可以是dp[i][k] + dp[k + 1][j] + cost

注意dp的时候的顺序，因为要求dp[1][n]，则需要用到dp[1][k]和dp[k][n]

你需要考虑下怎么for，才能使得子问题已经被算出，建议一开始用dfs + 记忆化做。

这里dp的顺序应该是先算出2个集合的，3个、4个、......

就是先算出dp[1][2], dp[2][3]，这使得求dp[1][3]成为可能。

all dp[i][i] = 0

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   const int maxn = 200 + 20;int n;int a[maxn];int dp[maxn][maxn];int sum[maxn];int dfs(int be, int en) { if (be > en) return 0; if (be == en) { return dp[be][en] = 0; } if (dp[be][en] != inf) return dp[be][en]; for (int k = be; k <= en; ++k) { dp[be][k] = dfs(be, k); dp[k + 1][en] = dfs(k + 1, en); assert(dp[be][k] >= 0); assert(dp[k + 1][en] >= 0); dp[be][en] = min(dp[be][k] + dp[k + 1][en] + sum[en] - sum[be - 1], dp[be][en]);// cout << dp[2][3] << endl; } return dp[be][en];}void work() { for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; } memset(dp, 0, sizeof dp);// cout << dfs(1, n) << endl;// cout << dp[2][3] << endl; for (int k = 1; k <= n - 1; ++k) { for (int i = 1; i <= n - 1; ++i) { int be = i; int en = i + k; if (en > n) break; dp[be][en] = inf; for (int h = be; h <= en - 1; ++h) { dp[be][en] = min(dp[be][en], dp[be][h] + dp[h + 1][en] + sum[en] - sum[be - 1]); } } } printf("%d\n", dp[1][n]);}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif while (scanf("%d", &n) != EOF) work(); return 0;}

View Code

平行四边形优化，其实我还不是很懂。那个证明太难了。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   int n;const int maxn = 1e3 + 20;int dp[maxn][maxn];int s[maxn][maxn];int sum[maxn];void work() { for (int i = 1; i <= n; ++i) { int x; scanf("%d", &x); sum[i] = sum[i - 1] + x; dp[i][i] = 0; s[i][i] = i; } for (int dis = 1; dis <= n - 1; ++dis) { for (int be = 1; be + dis <= n; ++be) { int en = be + dis; dp[be][en] = inf; int t = s[be][en]; for (int k = s[be][en - 1]; k <= s[be + 1][en]; ++k) { if (k + 1 > en) break; if (dp[be][en] >= dp[be][k] + dp[k + 1][en] + sum[en] - sum[be - 1]) { dp[be][en] = dp[be][k] + dp[k + 1][en] + sum[en] - sum[be - 1]; t = k; } } s[be][en] = t; } } cout << dp[1][n] << endl;}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif while (scanf("%d", &n) != EOF) work(); return 0;}