HDOJ - 3578 DP...巧妙構造DP狀态

2010年多校聯合的一道題...拿到手瞬間想到了POJ1014..以為是個水題..稍微加幾個條件直接01背包就ok了..如果K是<=所有數的和的一個偶數..能背出一個K..又能背出一個K/2...則說明K/2是答案..為了找最大的..就做完背包..從總和大小往前掃..找到了就break..找到最優解..立馬敲完代碼後各種WA~~~~後來發現了Bug...

 例如：

  典型dp

  dp[i][j]為拿到第i個橘子扁擔的兩個籃子重量差為j的最優情況，輸出dp[n][0]即可。

  小trick注意有重量為0的橘子，如果拿了重量為0的橘子并且兩邊重量依舊為0，這種情況不是-1。

好了..我這個小菜除了前面牢騷一下就不多說了...覺得這種題還是比較典型的....自己還木有這種思想啊~~！！！！

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int t,T,n,wight[101],TotolWight;
int GetMax(int a,int b)
{
    return a>b?a:b; 
}
int GetAbs(int x)
{
    return x<0?-x:x;   
}
int DP()
{
    int i,j,a[2][2001],k=0;
    memset(a,-1,sizeof(a));
    a[0][0]=0;
    for (i=1;i<=n;i++)
    {
       k=1-k;
       for (j=0;j<=TotolWight;j++) a[k][j]=a[1-k][j];
       for (j=0;j<=TotolWight-wight[i];j++)
         if (a[1-k][j]>=0)
           a[k][j+wight[i]]=GetMax(a[k][j+wight[i]],a[1-k][j]+wight[i]); 
       for (j=0;j<=TotolWight;j++)
         if (a[1-k][j]>=0) 
           a[k][GetAbs(j-wight[i])]=GetMax(a[k][GetAbs(j-wight[i])],a[1-k][j]+wight[i]); 
    } 
    if ( !a[k][0] && wight[1] ) return -1;
    return a[k][0]/2;
}
int main()
{
    freopen("3578.in","r",stdin);
    freopen("3578.out","w",stdout);
    scanf("%d",&T);
    for (t=1;t<=T;t++)
    {
       scanf("%d",&n); TotolWight=0;
       for (int i=1;i<=n;i++) 
       {
           scanf("%d",&wight[i]);
           TotolWight+=wight[i];
       }
       sort(wight+1,wight+1+n); 
       printf("Case %d: %d\n",t,DP()); 
    } 
    return 0;   
}