Lightoj 1031 - Easy Game DP

本文主要是介绍Lightoj 1031 - Easy Game DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

dp[i][j] 表示区间i到j先手取比后手取多多少

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include<functional>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int inf = 1<<30;
int n,m;
int num[maxn],sum[maxn],dp[maxn][maxn];
int main()
{#ifndef ONLINE_JUDGE  freopen("data.txt","r",stdin);  #endif 	int cas,c = 1;scanf("%d",&cas);while( cas -- ){scanf("%d",&n);sum[0] = 0;for( int i = 1; i <= n; i ++ ){scanf("%d",&num[i]);sum[i] = sum[i-1] + num[i];}for( int i = 1; i <= n; i ++ ){dp[i][i] = num[i];}for( int r = 0; r < n; r ++ ){for( int i = 1; i <= n; i ++ ){int j = i + r;dp[i][j] = -inf;for( int k = i; k < j; k ++ ){dp[i][j] = max(dp[i][j],max(sum[k]-sum[i-1]-dp[k+1][j],sum[j]-sum[k]-dp[i][k]));  //先取左边 先取右边}dp[i][j] = max( dp[i][j],sum[j] - sum[i-1]);}}printf("Case %d: %d\n",c++,dp[1][n]);}return 0;
}

这篇关于Lightoj 1031 - Easy Game DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---