HDOJ 4597 Play Game

3025 단어 HDOJ동적 계획
제목:A 와 B 는 한 게임 을 하고 두 개의 카드 가 있 습 니 다.한 장의 카드 에 하나의 포인트 가 있 습 니 다.두 사람 은 돌아 가면 서 한 조 의 맨 왼쪽 이나 맨 오른쪽 에서 한 장 을 찾 습 니 다.두 사람 은 모두 똑똑 합 니 다.가장 좋 은 방안 을 선택 하여 A 가 얻 은 포인트 와 가장 높 은 방안 을 선택한다.
링크:http://acm.hdu.edu.cn/showproblem.php?pid=4597
사고:구간 DP(기억 화 검색),취 하 는 방식 은 두 가지 에서 네 가지 로 바 뀌 었 습 니 다.상태 전이 방정식 은 ans=max(ans,sum-dfs(a-1,b,c,d),sum-dfs(a,b-1,c,d-1),sum-dfs(a,b,c-1,d),sum-dfs(a,b,c,d-1)입 니 다.
주의 점:경계 문 제 를 주의 하 세 요.처음에 경 계 를 고려 하지 않 고 빈 신의 코드 를 참고 하여 경계 문 제 를 발견 한 다음 에 A 가 되 었 습 니 다.
다음은 AC 코드 입 니 다.
Run ID
Submit Time
Judge Status
Pro.ID
Exe.Time
Exe.Memory
Code Len.
Language
Author
12433404
2014-12-08 21:07:22
Accepted
4597
109MS
4348K
2073 B
G++
luminous11 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define ull unsigned long long
#define all(x) (x).begin(), (x).end()
#define clr(a, v) memset( a , v , sizeof(a) )
#define pb push_back
#define mp make_pair
#define read(f) freopen(f, "r", stdin)
#define write(f) freopen(f, "w", stdout)
using namespace std;
int num1[30];
int num2[30];
int sum1[30];
int sum2[30];
int dp[30][30][30][30];
int sum = 0;
struct node
{
    int a;
    int b;
}cnt[2];
int dfs( int a, int b, int c, int d )
{
    int sum = 0;
    int ans = 0;
    if ( dp[a][b][c][d] != -1 )
        return dp[a][b][c][d];
    if ( a > b && c > d )
        return dp[a][b][c][d] = 0;
    if ( a <= b )
    {
        sum += sum1[b] - sum1[a-1];
    }
    if ( c <= d )
    {
        sum += sum2[d] - sum2[c-1];
    }
    if ( a <= b )
    {
        ans = max ( ans, sum - dfs (a + 1, b, c, d ) );
        ans = max ( ans, sum - dfs ( a, b - 1, c, d ) );
    }
    if ( c <= d )
    {
        ans = max ( ans, sum - dfs ( a, b, c + 1, d ) );
        ans = max ( ans, sum - dfs ( a, b, c, d - 1 ) );
    }
    return dp[a][b][c][d] = ans;
}
int main()
{
    ios::sync_with_stdio( false );
    int t;
    cin >> t;
    while ( t -- )
    {
        int k;
        cin >> k;
        memset ( dp, -1, sizeof ( dp ) );
        memset ( sum1, 0, sizeof ( sum1 ) );
        memset ( sum2, 0, sizeof ( sum2 ) );
        for ( int i = 1; i <= k; i ++ )
        {
            cin >> num1[i];
            sum1[i] = sum1[i-1] + num1[i];
        }
        for ( int i = 1; i <= k; i ++ )
        {
            cin >> num2[i];
            sum2[i] = sum2[i-1] + num2[i];
        }
        cout << dfs( 1, k, 1, k ) << endl;

    }
    return 0;
}
Mina IoService?????????
ZOJ 3016 Cut(이산 화+최소 생 성 트 리)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage