「JoyOI1088」treat

2014年2月5日2,7840

题目描述

给出长度为N的数列{A_i}，每次可以从最左边或者最右边取走一个数，第i次取数得到的价值是i * A_j。求价值之和最大的取数方案。

输入

第一行，一个整数，表示数列长度N。接下来N行，每行一个整数，表示数列A_i。

输出

一个整数，表示最大的价值之和。

样例输入

5 1 3 1 5 2

样例输出

提示

N < = 2000 , A_i < = 1000

题解

dp或者记忆化搜索。。

f[i][j]表示左边取i个右边j个最大价值，方程比较好想。。

for(int i=0;i<=n;i++)
       for(int j=0;j<=n;j++)
          f[i][j]=max(f[i-1][j]+(i+j)*a[i],f[i][j-1]+(i+j)*a[n-j+1]);

for(int i=0;i<=n;i++)

for(int j=0;j<=n;j++)

f[i][j]=max(f[i-1][j]+(i+j)*a[i],f[i][j-1]+(i+j)*a[n-j+1]);

但是注意会有负数，所以都加上1

#include<iostream>
#include<cstdio>
using namespace std;
int f[2005][2005];
int n,a[2005],ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=0;i<=n;i++)
       for(int j=0;j<=n-i;j++)
          f[i+1][j+1]=max(f[i][j+1]+(i+j)*a[i],f[i+1][j]+(i+j)*a[n-j+1]);
    for(int i=0;i<=n;i++)ans=max(ans,f[i+1][n-i+1]);
    printf("%d",ans);
    return 0;
    }

#include<iostream>

#include<cstdio>

using namespace std;

int f[2005][2005];

int n,a[2005],ans=0;

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)scanf("%d",&a[i]);

for(int i=0;i<=n;i++)

for(int j=0;j<=n-i;j++)

f[i+1][j+1]=max(f[i][j+1]+(i+j)*a[i],f[i+1][j]+(i+j)*a[n-j+1]);

for(int i=0;i<=n;i++)ans=max(ans,f[i+1][n-i+1]);

printf("%d",ans);

return 0;

}

« 「CODEVS1403」新三国争霸「BZOJ1040」[ZJOI2008] 骑士 »

hzwer.com _ Home | http://hzwer.com

「JoyOI1088」treat

题目描述

输入

输出

样例输入

样例输出

提示

题解

分类目录

热门文章

Myfriends

近期评论