C言語記憶検索_Play Game(Hdu 4597)
3682 ワード
Play Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 822 Accepted Submission(s): 474
Problem Description
Alice and Bob are playing a game. There are two piles of cards. There are N cards in each pile, and each card has a score. They take turns to pick up the top or bottom card from either pile, and the score of the card will be added to his total score. Alice and Bob are both clever enough, and will pick up cards to get as many scores as possible. Do you know how many scores can Alice get if he picks up first?
Input
The first line contains an integer T (T≤100), indicating the number of cases. Each case contains 3 lines. The first line is the N (N≤20). The second line contains N integer ai (1≤ai≤10000). The third line contains N integer bi (1≤bi≤10000).
Output
For each case, output an integer, indicating the most score Alice can get.
Sample Input
Sample Output
标题:二山のカードがあり、一山ごとに同じ数のカードがあり、しかも一枚のカードに数字がある.今、A、Bは交代でこの二山のカードの中から一枚のカードを抽出する(毎回抽出するのは上部または下部からしか抽出できない).すべてのカードを抽出した後、一人一人が抽出したカードの数字はできるだけ大きく、AB二人が十分に頭がいいと仮定する.Aの最后の数字の総和を闻きます.各グループのテストデータは3行あって、第1行はカードの山の数ごとに、第2行と第3行はそれぞれ2対のカードの上で対応する数字で、Aの最后の数字の総和を出力します.
分析:
この問題は区間dpと言えるでしょう.この問題の原型を見てみましょう. 他のルールはすべて同じで、しかし1つの数字のシーケンスだけあって、毎回左右の両端の1つの数字しか持っていないので、最終的にアリスにいくら取りますか? 1行の数字のシーケンスだけがf(i,j)で数字のシーケンスがまだ区間[i,j]のセグメントを残していることを表すことができて、最大でどれだけの数字を持つことができます この問題は2行の数字のシーケンスになっただけで、上の基礎の上で、更に2次元を増加することができます f(i,j,k,l)となり、1つ目のシーケンスが区間[i,j]を残し、2つ目のシーケンスが区間[k,l]を残した場合に取り始めることを示しますが、どれくらいまで取れるのでしょうか? 状態f(i,j,k,l)に直面すると、4つの選択肢があります. 1.最初の行の一番左の数字を選択 2.最初の行の右端の数字を選択 3.2行目の一番左の数字を選択 4.2行目の右端の数字を選択 したがって、f(i,j,k,l)は、 f(i+1, j, k, l) f(i, j-1, k, l) f(i, j, k+1, l) f(i, j, k, l-1) この4つの状態が移行し、 現在の状態がAliceが選択すると仮定すると、前の状態がBob選択の最大値であり、 Aliceの最終と最大にするには、上の4つの状態の最小の1つを選択します. sum(i,j,k,l)が表す1つのシーケンス[i,j]セグメントの和と2番目のシーケンスの[k,l]セグメントの和の和とする.
sum(i, j, k, l) - 前回ボブが取った値はアリスが手に入れた値に等しい.
f(i, j, k, l) = sum(i, j, k, l) -min{ f(i+1, j, k, l), f(i, j-1, k, l), f(i, j, k+1, l), f(i, j, k, l-1) };
上のコード:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 822 Accepted Submission(s): 474
Problem Description
Alice and Bob are playing a game. There are two piles of cards. There are N cards in each pile, and each card has a score. They take turns to pick up the top or bottom card from either pile, and the score of the card will be added to his total score. Alice and Bob are both clever enough, and will pick up cards to get as many scores as possible. Do you know how many scores can Alice get if he picks up first?
Input
The first line contains an integer T (T≤100), indicating the number of cases. Each case contains 3 lines. The first line is the N (N≤20). The second line contains N integer ai (1≤ai≤10000). The third line contains N integer bi (1≤bi≤10000).
Output
For each case, output an integer, indicating the most score Alice can get.
Sample Input
2 1 23 53 3 10 100 20 2 4 3
Sample Output
53 105
标题:二山のカードがあり、一山ごとに同じ数のカードがあり、しかも一枚のカードに数字がある.今、A、Bは交代でこの二山のカードの中から一枚のカードを抽出する(毎回抽出するのは上部または下部からしか抽出できない).すべてのカードを抽出した後、一人一人が抽出したカードの数字はできるだけ大きく、AB二人が十分に頭がいいと仮定する.Aの最后の数字の総和を闻きます.各グループのテストデータは3行あって、第1行はカードの山の数ごとに、第2行と第3行はそれぞれ2対のカードの上で対応する数字で、Aの最后の数字の総和を出力します.
分析:
この問題は区間dpと言えるでしょう.この問題の原型を見てみましょう. 他のルールはすべて同じで、しかし1つの数字のシーケンスだけあって、毎回左右の両端の1つの数字しか持っていないので、最終的にアリスにいくら取りますか? 1行の数字のシーケンスだけがf(i,j)で数字のシーケンスがまだ区間[i,j]のセグメントを残していることを表すことができて、最大でどれだけの数字を持つことができます この問題は2行の数字のシーケンスになっただけで、上の基礎の上で、更に2次元を増加することができます f(i,j,k,l)となり、1つ目のシーケンスが区間[i,j]を残し、2つ目のシーケンスが区間[k,l]を残した場合に取り始めることを示しますが、どれくらいまで取れるのでしょうか? 状態f(i,j,k,l)に直面すると、4つの選択肢があります. 1.最初の行の一番左の数字を選択 2.最初の行の右端の数字を選択 3.2行目の一番左の数字を選択 4.2行目の右端の数字を選択 したがって、f(i,j,k,l)は、 f(i+1, j, k, l) f(i, j-1, k, l) f(i, j, k+1, l) f(i, j, k, l-1) この4つの状態が移行し、 現在の状態がAliceが選択すると仮定すると、前の状態がBob選択の最大値であり、 Aliceの最終と最大にするには、上の4つの状態の最小の1つを選択します. sum(i,j,k,l)が表す1つのシーケンス[i,j]セグメントの和と2番目のシーケンスの[k,l]セグメントの和の和とする.
sum(i, j, k, l) - 前回ボブが取った値はアリスが手に入れた値に等しい.
f(i, j, k, l) = sum(i, j, k, l) -min{ f(i+1, j, k, l), f(i, j-1, k, l), f(i, j, k+1, l), f(i, j, k, l-1) };
上のコード:
#include <stdio.h>
#include <string.h>
int dp[30][30][30][30];
int arr1[30],arr2[30],sum1[30],sum2[30];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
int dfs(int l1,int r1,int l2,int r2)
{
if(dp[l1][r1][l2][r2]!=-1)return dp[l1][r1][l2][r2];
if(l1>r1&&l2>r2) return dp[l1][r1][l2][r2]=0;
int ans=0;
int sum=0;
if(l1<=r1) sum+=sum1[r1]-sum1[l1-1];
if(l2<=r2) sum+=sum2[r2]-sum2[l2-1];
if(l1<=r1)
{
ans=max(ans,sum-dfs(l1+1,r1,l2,r2));
ans=max(ans,sum-dfs(l1,r1-1,l2,r2));
}
if(l2<=r2)
{
ans=max(ans,sum-dfs(l1,r1,l2+1,r2));
ans=max(ans,sum-dfs(l1,r1,l2,r2-1));
}
return dp[l1][r1][l2][r2]=ans;
}
int main()
{
int T,i,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&arr1[i]);
sum1[i]=sum1[i-1]+arr1[i];
}
for(i=1;i<=n;i++)
{
scanf("%d",&arr2[i]);
sum2[i]=sum2[i-1]+arr2[i];
}
memset(dp,-1,sizeof(dp));
printf("%d
",dfs(1,n,1,n));
}
return 0;
}