Yui的狗窝
Yui的狗窝
hihocoder 1338 A Game 动态规划

原题:https://hihocoder.com/problemset/problem/1338
题目大意:给出一个数列,ho先取数字,每次只能取数列的头和尾部数据,求ho可取到的最大数字和。
知道了是动态规划类型的题目以后就显得很简单,列表格使用数归求出推导式。

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1001;
int N,res;
int A[MAXN],sum[MAXN][MAXN],f[MAXN][MAXN];
int sol()
{
    for(int i=1;i<=N;i++)
        f[i][i]=A[i];
    for(int i=1;i!=N;i++)
    {
        int left=N-i,right=N;
        while(left!=0)
        {
            f[left][right]=max(sum[left][right]-f[left+1][right],sum[left][right]-f[left][right-1]);
            left--;right--;
        }
    }
    return f[1][N];
}
int main()
{
    while(cin>>N)
    {
        res=0;
        cin>>A[1];
        for(int i=2;i<=N;i++)
            cin>>A[i];
        for(int i=1;i<=N;i++)
        {
            sum[i][i]=A[i];
            for(int j=i+1;j<=N;j++)
                sum[i][j]=sum[i][j-1]+A[j];
        }
        cout<<sol()<<endl;
    }
}
没有标签
首页      算法训练      hihocoder 1338 A Game 动态规划
https://secure.gravatar.com/avatar/d0fe7f1b17d5e9122db921e3a8cc327f?s=256&d=mm&r=g

Suzumiya, Yui

文章作者

发表评论

textsms
account_circle
email

Yui的狗窝

hihocoder 1338 A Game 动态规划
原题:https://hihocoder.com/problemset/problem/1338 题目大意:给出一个数列,ho先取数字,每次只能取数列的头和尾部数据,求ho可取到的最大数字和。 知道了是动态规划类型的题目以后就…
扫描二维码继续阅读
2017-10-31


没有激活的小工具