首页 > 代码库 > HDU 4597

HDU 4597

2024-07-21 10:53:47   219人阅读

题目大意：

两人轮流从两堆牌从抽取最顶端或者最底部的牌，得到的分数加到自己身上，问先拿牌的最多能得多少分

 

记忆化搜索，2堆牌的底和顶，有四种方法，根据四种方法来找到最优解

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 int dp[22][22][22][22],p[22],q[22]; 6 int dfs(int a,int b,int c,int d,int sum) 7 { 8     int maxn=0; 9     if(a>b&&c>d) return 0;10     if(dp[a][b][c][d]) return dp[a][b][c][d];11     if(a<=b){12         maxn=max(maxn,sum-dfs(a+1,b,c,d,sum-p[a]));13         maxn=max(maxn,sum-dfs(a,b-1,c,d,sum-p[b]));14     }15     if(c<=d){16         maxn=max(maxn,sum-dfs(a,b,c+1,d,sum-q[c]));17         maxn=max(maxn,sum-dfs(a,b,c,d-1,sum-q[d]));18     }19     dp[a][b][c][d]=maxn;20     return maxn;21 }22 int main()23 {24     int T,n,sum;25     scanf("%d",&T);26     while(T--){27         sum=0;28         scanf("%d",&n);29         for(int i=1;i<=n;i++){30             scanf("%d",&p[i]);31             sum+=p[i];32         }33         for(int i=1;i<=n;i++){34             scanf("%d",&q[i]);35             sum+=q[i];36         }37         memset(dp,0,sizeof(dp));38         int ans=dfs(1,n,1,n,sum);39         printf("%d\n",ans);40     }41     return 0;42 }

 

HDU 4597


联系
我们