uva10118 Free Candies（DP）

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=1059

此题的状态即为4个栈的顶部元素的位置

#include <iostream>
#include <set>
#include <stack>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;
stack<int> st[5];
vector<int> v[5];
int n,num;
ll dp[42][42][42][42];
bool vis[22];
set<int> cc;
set<int>::iterator it;
void read(){
    cc.clear();
    int x;
    for(int i=0;i<n;i++){
        for(int j=1;j<=4;j++){
            cin>>x;
            st[j].push(x);
            cc.insert(x);
        }
    }
    for(int i=1;i<=4;i++) v[i].clear();
    for(int i=1;i<=4;i++){
        while(!st[i].empty()){
            v[i].push_back(st[i].top());
            st[i].pop();
        }
    }
}
ll DP(int s1,int s2,int s3,int s4){
    if(num>=5) return 0;
    if(s1+s2+s3+s4==0) return 0;
    if(dp[s1][s2][s3][s4]!=-1) return dp[s1][s2][s3][s4];
    //cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<endl;
    ll ret=0;
    for(int i=1;i<=4;i++){
        if(v[i].size()==0) continue;
        int now=v[i][v[i].size()-1],take_num=0;
        v[i].pop_back();
        if(!vis[now]){
           vis[now]=1;
        }else{
           vis[now]=0;
           take_num=1;
        }
        int past=num;
        num=0;
        for(it=cc.begin();it!=cc.end();it++){
            if(vis[*it]) num++;
        }
        /*cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<endl;
        for(it=cc.begin();it!=cc.end();it++){
            if(vis[*it]) cout<<(*it)<<" ";
        }
        cout<<endl;
        cout<<i<<" "<<num<<" "<<take_num<<endl;*/
        if(i==1) ret=max(ret,DP(s1-1,s2,s3,s4)+take_num);
        else if(i==2) ret=max(ret,DP(s1,s2-1,s3,s4)+take_num);
        else if(i==3) ret=max(ret,DP(s1,s2,s3-1,s4)+take_num);
        else ret=max(ret,DP(s1,s2,s3,s4-1)+take_num);
        v[i].push_back(now);
        if(!take_num) vis[now]=0;
        else vis[now]=1;
        num=past;
    }
    //cout<<s1<<" "<<s2<<" "<<s3<<" "<<s4<<" "<<num<<" "<<ret<<endl;
    return dp[s1][s2][s3][s4]=ret;
}
void gao(){
    num=0;
    memset(dp,-1,sizeof dp);
    memset(vis,0,sizeof vis);
    cout<<DP(n,n,n,n)<<endl;
}
int main(){
    //freopen("10118","r",stdin);
    while(~scanf("%d",&n)&&n){
        read();
        gao();
    }
    return 0;
}