2010年03月20日星期六.sgu256.cc dp
我看到这题的第一印象就是，这可能是个水题。但是我错了。
这个题一看就是个dp，于是我就写了个5层循环的dp，死活不知道怎么错了。
后来看到了scau的代码，发现递推式基本相同，不同的是他写的是记忆化搜索.
然后我也就写了个记忆话搜索，也过了。。
1
2 #include<iostream>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cstring>
6 #include<algorithm>
7 using namespace std;
8 typedef long long LL;
9 const int maxint = 0x7fffffff;
10 const long long max64 = 0x7fffffffffffffffll;
11 const int Debug = 1;
12 const int M = 228;
13 const int N = 13;
14 const int inf = 1000000;
15
16 int dp[M][N][N][N][N], m, n, a[N], b[N];
17 void ckmin(int &a, int b) { if (a > b) { a = b; } }
18 int dfs(int balloon,int p0,int p1,int p2,int p3)
19 {
20 if (dp[balloon][p0][p1][p2][p3] < inf) {
21 return dp[balloon][p0][p1][p2][p3];
22 }
23 if (balloon >= m) {
24 return 0;
25 }
26 for (int i = 1;i <= n;i++) {
27 if (b[i] == 1 && (p0 == i)) { continue; }
28 if (b[i] == 2 && (p0 == i || p1 == i)) { continue; }
29 if (b[i] == 3 && (p0 == i || p1 == i || p2 == i)) { continue; }
30 if (b[i] == 4 && (p0 == i || p1 == i || p2 == i || p3 == i)) { continue; }
31 ckmin(dp [balloon][p0][p1][p2][p3] , dfs(balloon + a[i],i,p0,p1,p2) + 1);
32 }
33 if (dp [balloon][p0][p1][p2][p3] >= inf) {
34 dp [balloon][p0][p1][p2][p3] = dfs(balloon,0,p0,p1,p2) + 1;
35 }
36 return dp [balloon][p0][p1][p2][p3];
37 }
38//http://www.cppblog.com/schindlerlee
39 int main()
40 {
41 int i, j, k, p[4], tmp;
42 memset(dp,127,sizeof(dp));
43 //printf("%d\n",dp[0][0][0][0][0]);
44 scanf("%d %d", &m, &n);
45 for (i = 1; i <= n; i++) {
46 scanf("%d %d", a + i, b + i);
47 }
48
49 printf("%d\n", dfs(0,0,0,0,0));
50 return 0;
51 }
52