Why so serious? --[NKU]schindlerlee

2010年03月20日星期六.sgu256.cc dp

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 

posted on 2010-03-20 13:54 schindlerlee 阅读(1184) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理