NK1137 石子合並問題

題意：石子合並問題。DP問題。

我們先來考慮一條直線的問題，最小花費和最大花費方法是一樣的，我們只考慮一種：我們先考慮一個子問題，要把從i 到j 的石子合並成一堆，肯定要先把它們合並成兩堆；由於只允許相鄰兩堆合並，必然是i 到j 之間被分成了兩段，設這個中間點是k，則這個方案可以表示為先把i 到k 合並，再把k + 1 到j 合並，然
後把得到的兩堆合並，最後一次合並的花費為i 到j 所有石子的質量和，所以我們有dp[i; j] = min(dp[i; k] + dp[k + 1; j]) + weight[i; j]，簡單地得到了O(N3) 的方法。

如果要考慮環的話，只需依次選擇不同的頭，即拆成n條不同的線段即可。

[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <vector>  
#include <queue>  
#include <algorithm>  
using namespace std; 
 
#define INF 0x3f3f3f3f  
 
int a[105]; 
int dp[105][105][2]; 
int n; 
int mmax,mmin; 
 
int weight(int i,int j) 
{ 
    int sum = 0; 
    for(int k=i;k<=j;k++) sum+=a[k]; 
    return sum; 
} 
void solve() 
{ 
    memset(dp,0,sizeof(dp)); 
    for(int i = n-1;i>=1;i--) 
    { 
        for(int j = i+1;j<=n;j++) 
        { 
            dp[i][j][0] = -INF,dp[i][j][1] = INF; 
            for(int k = i;k<j;k++) 
            { 
                dp[i][j][0] = max(dp[i][j][0],dp[i][k][0] + dp[k+1][j][0] + weight(i,j)); 
                dp[i][j][1] = min(dp[i][j][1],dp[i][k][1] + dp[k+1][j][1] + weight(i,j)); 
            } 
        } 
    } 
    mmax = max(mmax,dp[1][n][0]); 
    mmin = min(mmin,dp[1][n][1]); 
} 
 
int main() 
{ 
#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    while(scanf(" %d",&n)!=EOF) 
    { 
        mmax = -INF,mmin = INF; 
        for(int i=1;i<=n;i++) scanf(" %d",&a[i]); 
        solve(); 
        for(int i=2;i<=n;i++) 
        { 
            int last = a[1]; 
            for(int i=1;i<n;i++) a[i] = a[i+1]; 
            a[n] = last; 
            solve(); 
        } 
        printf("%d\n",mmin); 
        printf("%d\n",mmax); 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f

int a[105];
int dp[105][105][2];
int n;
int mmax,mmin;

int weight(int i,int j)
{
    int sum = 0;
    for(int k=i;k<=j;k++) sum+=a[k];
    return sum;
}
void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i = n-1;i>=1;i--)
    {
        for(int j = i+1;j<=n;j++)
        {
            dp[i][j][0] = -INF,dp[i][j][1] = INF;
            for(int k = i;k<j;k++)
            {
                dp[i][j][0] = max(dp[i][j][0],dp[i][k][0] + dp[k+1][j][0] + weight(i,j));
                dp[i][j][1] = min(dp[i][j][1],dp[i][k][1] + dp[k+1][j][1] + weight(i,j));
            }
        }
    }
    mmax = max(mmax,dp[1][n][0]);
    mmin = min(mmin,dp[1][n][1]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    while(scanf(" %d",&n)!=EOF)
    {
        mmax = -INF,mmin = INF;
        for(int i=1;i<=n;i++) scanf(" %d",&a[i]);
        solve();
        for(int i=2;i<=n;i++)
        {
            int last = a[1];
            for(int i=1;i<n;i++) a[i] = a[i+1];
            a[n] = last;
            solve();
        }
        printf("%d\n",mmin);
        printf("%d\n",mmax);
    }
    return 0;
}