hdu 2452+hdu 1501

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2452

http://acm.hdu.edu.cn/showproblem.php?pid=1501

记忆化搜索。。。说的简单点，就是dfs+状态标记。。。

View Code

 1 #include<iostream>
 2 #include<vector>
 3 const int MAXN=10000+10;
 4 const int inf=1<<30;
 5 using namespace std;
 6 int n,m,f;
 7 vector<int>mp[MAXN];
 8 int value[MAXN];
 9 int In[MAXN],Out[MAXN];
10 int dp[MAXN][2];
11 
12 int dfs(int now,int mark){
13     //vector做决定
14     if(mark==1){
15         if(dp[now][1]!=-1){
16             return dp[now][1];
17         }
18         int MAX=0;
19         for(int i=0;i<mp[now].size();i++){
20             int ans=dfs(mp[now][i],0);//状态发生变化
21             if(ans>MAX)MAX=ans;
22         }
23         dp[now][1]=MAX+value[now];
24         return dp[now][1];
25     }else {
26         if(dp[now][0]!=-1){
27             return dp[now][0];
28         }
29         int MIN=inf;
30         for(int i=0;i<mp[now].size();i++){
31             int ans=dfs(mp[now][i],1);
32             if(ans<MIN)MIN=ans;
33         }
34         if(MIN==inf)dp[now][0]=value[now];
35         else dp[now][0]=MIN+value[now];
36         return dp[now][0];
37     }
38 }
39 
40 int main(){
41     while(~scanf("%d%d%d",&n,&m,&f)){
42         memset(In,0,sizeof(In));
43         memset(Out,0,sizeof(Out));
44         memset(dp,-1,sizeof(dp));
45         for(int i=1;i<=n;i++){
46             scanf("%d",&value[i]);
47             mp[i].clear();
48         }
49         for(int i=1;i<=m;i++){
50             int x,y;
51             scanf("%d%d",&x,&y);
52             In[y]++,Out[x]++;
53             mp[x].push_back(y);
54         }
55         int start=1;
56         //找入口
57         for(int i=1;i<=n;i++)if(In[i]==0){
58             start=i;
59             break;
60         }
61         int ans=dfs(start,1);//1-vector,0-glory;
62         if(ans>=f){
63             printf("Victory\n");
64         }else 
65             printf("Glory\n");
66     }
67     return 0;
68 }

View Code

 1 #include<iostream>
 2 #include<cstring>
 3 const int MAXN=222;
 4 using namespace std;
 5 int len1,len2,len;
 6 char str1[MAXN],str2[MAXN],str[MAXN<<1];
 7 bool mark[MAXN][MAXN];
 8 
 9 
10 bool dfs(int pos1,int pos2,int pos){
11     if(pos==len){
12         return true;
13     }
14     if(mark[pos1][pos2])return false;
15     mark[pos1][pos2]=true;
16     if(str1[pos1]==str[pos]){
17         if(dfs(pos1+1,pos2,pos+1))return true;
18     }
19     if(str2[pos2]==str[pos]){
20         if(dfs(pos1,pos2+1,pos+1))return true;
21     }
22     return false;
23 }
24 
25 
26 int main(){
27     int _case,k=1;
28     scanf("%d",&_case);
29     while(_case--){
30         scanf("%s%s%s",str1,str2,str);
31         printf("Data set %d: ",k++);
32         len1=strlen(str1);
33         len2=strlen(str2);
34         len=strlen(str);
35         memset(mark,false,sizeof(mark));
36         if(len1+len2!=len){
37             printf("no\n");
38         }else if(dfs(0,0,0)){
39             printf("yes\n");
40         }else 
41             printf("no\n");
42     }
43     return 0;
44 }