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
");

64         }else 

65             printf("Glory
");

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
");

38         }else if(dfs(0,0,0)){

39             printf("yes
");

40         }else 

41             printf("no
");

42     }

43     return 0;

44 }