vijos 1037 搭建雙塔 簡單DP

2001年9月11日，一場突發的災難將紐約世界貿易中心大廈夷為平地，Mr. F曾親眼目睹了這次災難。為了紀念“9?11”事件，Mr. F決定自己用水晶來搭建一座雙塔。
　　Mr. F有N塊水晶，每塊水晶有一個高度，他想用這N塊水晶搭建兩座有同樣高度的塔，使他們成為一座雙塔，Mr. F可以從這N塊水晶中任取M（1≤M≤N）塊來搭建。但是他不知道能否使兩座塔有同樣的高度，也不知道如果能搭建成一座雙塔，這座雙塔的最大高度是多少。所以他來請你幫忙。

　　給定水晶的數量N（1≤N≤100）和每塊水晶的高度Hi（N塊水晶高度的總和不超過2000），你的任務是判斷Mr. F能否用這些水晶搭建成一座雙塔（兩座塔有同樣的高度），如果能，則輸出所能搭建的雙塔的最大高度，否則輸出“Impossible”。

一看就跟背包有些類似，實際上確實是個很簡單的DP

用dp[i][j] 表示的是前i個水晶，湊成的兩塔高度差為j的較低塔的最大高度。

那麼它的狀態可能由四種情況轉化而來

1.該物品沒用上

2.低塔加上了該物品還是低塔

3.高塔加上了該物品邊的更高了

4.低塔加上了該物品變成了高塔

這裡我們可以畫幾個圖，就清晰許多了

轉移方程請看代碼

[cpp] view plaincopyprint?#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <vector>  
#include <queue>  
#include <set>  
#include <stack>  
#include <map>  
#define MAXN 777  
#define MAXM 400005  
#define INF 1000000007  
using namespace std; 
int n; 
int f[111][2222], c[111]; 
int main() 
{ 
    scanf("%d", &n); 
    int sum = 0; 
    for(int i = 1; i <= n; i++) 
    { 
        scanf("%d", &c[i]); 
        sum += c[i]; 
    } 
    memset(f, -1, sizeof(f)); 
    f[0][0] = 0; 
    for(int i = 1; i <= n; i++) 
    { 
        for(int j = 0; j <= sum; j++) 
        { 
            if(f[i - 1][j] != -1) f[i][j] = f[i - 1][j]; 
            if(j + c[i] <= sum && f[i - 1][j + c[i]] != -1) 
                f[i][j] = max(f[i][j], f[i - 1][j + c[i]] + c[i]); 
            if(j >= c[i] && f[i - 1][j - c[i]] != -1) 
                f[i][j] = max(f[i][j], f[i - 1][j - c[i]]); 
            if(c[i] > j && f[i - 1][c[i] - j] != -1) 
                f[i][j] = max(f[i][j], f[i - 1][c[i] - j] + c[i] - j); 
        } 
    } 
    if(f[n][0] > 0) printf("%d\n", f[n][0]); 
    else printf("Impossible\n"); 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#define MAXN 777
#define MAXM 400005
#define INF 1000000007
using namespace std;
int n;
int f[111][2222], c[111];
int main()
{
    scanf("%d", &n);
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &c[i]);
        sum += c[i];
    }
    memset(f, -1, sizeof(f));
    f[0][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= sum; j++)
        {
            if(f[i - 1][j] != -1) f[i][j] = f[i - 1][j];
            if(j + c[i] <= sum && f[i - 1][j + c[i]] != -1)
                f[i][j] = max(f[i][j], f[i - 1][j + c[i]] + c[i]);
            if(j >= c[i] && f[i - 1][j - c[i]] != -1)
                f[i][j] = max(f[i][j], f[i - 1][j - c[i]]);
            if(c[i] > j && f[i - 1][c[i] - j] != -1)
                f[i][j] = max(f[i][j], f[i - 1][c[i] - j] + c[i] - j);
        }
    }
    if(f[n][0] > 0) printf("%d\n", f[n][0]);
    else printf("Impossible\n");
    return 0;
}