2010年03月20日星期六.sgu256.cc dp
我看到這題的第一印象就是，這可能是個(gè)水題。但是我錯(cuò)了。
這個(gè)題一看就是個(gè)dp，于是我就寫了個(gè)5層循環(huán)的dp，死活不知道怎么錯(cuò)了。
后來看到了scau的代碼，發(fā)現(xiàn)遞推式基本相同，不同的是他寫的是記憶化搜索.
然后我也就寫了個(gè)記憶話搜索，也過了。。
?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://m.shnenglu.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?