HDu 4597(記憶化検索)
7479 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=4597
構想:現在の状態で、得られるのが最も優れていることを保証するには、dfs+dp.
View Code
構想:現在の状態で、得られるのが最も優れていることを保証するには、dfs+dp.
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6
7 int Left[44],Right[44];
8 int dp[22][22][22][22];
9 int n,ans,MAX;
10
11 int dfs(int upl,int downl,int upr,int downr,int sum)
12 {
13 if(dp[upl][downl][upr][downr])return dp[upl][downl][upr][downr];
14 int ans=0;
15 if(upl<=downl){
16 ans=max(ans,sum-dfs(upl+1,downl,upr,downr,sum-Left[upl]));
17 ans=max(ans,sum-dfs(upl,downl-1,upr,downr,sum-Left[downl]));
18 }
19 if(upr<=downr){
20 ans=max(ans,sum-dfs(upl,downl,upr+1,downr,sum-Right[upr]));
21 ans=max(ans,sum-dfs(upl,downl,upr,downr-1,sum-Right[downr]));
22 }
23 return dp[upl][downl][upr][downr]=ans;
24 }
25
26 int main()
27 {
28 // freopen("1.txt","r",stdin);
29 int _case,sum;
30 scanf("%d",&_case);
31 while(_case--){
32 scanf("%d",&n);
33 for(int i=1;i<=n;i++)scanf("%d",&Left[i]),sum+=Left[i];
34 for(int i=1;i<=n;i++)scanf("%d",&Right[i]),sum+=Right[i];
35 memset(dp,0,sizeof(dp));
36 if(n==1){
37 printf("%d
",max(Left[1],Right[1]));
38 continue;
39 }
40 printf("%d
",dfs(1,n,1,n,sum));
41 }
42 return 0;
43 }
View Code