zoj 3554 A Miser Boss

题意:a、b、cの3人が同时に働いて、3人が异なる任务をして异なる时间を必要として、しかし最后に3人が事をする総时间が同じであることを要求して、出力してすべての任务を完成して必要とする最小の时间を必要として、もし3人の総仕事の时间が同じでないならば、“No”
 
当時、頭筋は最大流や他の図論のものだと感じ、dpにも考えたが、状態表示さえ考えられなかった.それから大牛たちのやり方を参考にして、標準的なやり方はbfsのすべての可能性のある状況で、それからもう一つかっこいいです.このbfsは久しぶりに書いたので、しばらく書いていません.
 
もう一つの巧妙な方法があります

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 250    //maxn  250   250>=120*2 
#define see(x) cout<<#x<<":"<<x<<endl;
short dp[41][maxn][maxn];
void adjust(short &x, short y){
    if(x==-1||x>y){
        x = y;
    }
}
int main(){
    int n, a, b, c;
    int i, j, k, l;
    while(~scanf("%d",&n)){
        memset(dp,-1,sizeof(dp));
        dp[0][121][121] = 0;   //       121 ，        
//              0、1 ，    ，    ，121     120   0，  120   maxn   
        for(i=0;i<n;i++){
            scanf("%d%d%d",&a,&b,&c);
        //    see(i)
            for(j=0;j<maxn;j++){
                for(k=0;k<maxn;k++){
                    if(dp[i][j][k]>=0){   //         ，       0，     -1       
        //               ，                dp[0][121][121]   ，  -1<0     ！！！ 
                        if(j+a<maxn){
                            adjust(dp[i+1][j+a][k],dp[i][j][k]+a);
                        }
                        if(j-b>=0&&k+b<maxn){
                            adjust(dp[i+1][j-b][k+b],dp[i][j][k]+b);
                        }
                        if(k-c>=0){
                            adjust(dp[i+1][j][k-c],dp[i][j][k]+c);
                        }
                    }
                }
            }
            //see(dp[i+1][121][121])
        }
        if(dp[n][121][121]==-1){
            printf("NO
");
        }
        else{
            printf("%d
",dp[n][121][121]/3);
        }
    }
    return 0;
}