uva10817 校长的烦恼 利用-ans

1. 利用int& ans保存当前状态，因为他不会随着下标的改变而改变，防止下表改变而出现的bug。
2. 增加维度来解决状态的表示，找明白状态，决策，状态转换。
3. 通过记忆化来枚举所有可以完成规定任务的代价看哪个少，通过赋值INF 和 0 来方便比较。

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19472

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<ctime>
#include<vector>
#include<fstream>
#include<list>
using namespace std;

#define ms(s) memset(s,0,sizeof(s))
typedef long long LL;
typedef unsigned long long ULL;

const int INF = 1000000000;
const int maxmn = 120 + 5;
const int maxs = 255+3;
int m, n, s;
int c[maxmn];
int p[maxmn];
int d[maxmn][maxs][maxs];
int s0, s1, s2;

int dp(int i, int s0, int s1, int s2)
{
// cout<<" i: "<<i<<" s0: "<<s0<<" s1: "<<s1<<" s2: "<<s2<<endl;

if(i == m+n)//return ans
    {
if(s2 == (1<<s)-1)
return 0;
else
return INF;
    }
int& ans = d[i][s1][s2];
if(ans >= 0)
return ans;//memorize
    ans = INF;
if(i >= m)
        ans = dp(i+1, s0, s1, s2);
int m0 = p[i] & s0, m1 = p[i] & s1;
    s0 ^= m0;//update the subject
    s1 = (s1 ^ m1) | m0;
    s2 |= m1;

    ans = min(ans,c[i]+dp(i+1, s0, s1, s2));
return ans;
}

int main()
{
// freopen("F:\\data.txt","r",stdin);//方便调试
int t;
string strt;
while(getline(cin, strt))
    {
stringstream ss(strt);
        ss >> s >> m >> n;
if(s==0)
break;
        ms(c);
        ms(p);
memset(d,-1,sizeof(d));

for(int i = 0; i < m+n; i++)
        {
            getline(cin,strt);
stringstream ss(strt);
            ss >> c[i];
            p[i] = 0;
while(ss >> t)
                p[i] |= (1<<(t-1));
        }
int tt = dp(0, (1<<s)-1, 0, 0);
printf("%d\n",tt);
    }


return 0;
}