描述 Description
给出长度为N的数列{A_i},每次可以从最左边或者最右边取走一个数,第i次取数得到的价值是i * A_j。求价值之和最大的取数方案。
输入格式 Input Format
第一行,一个整数,表示数列长度N。
接下来N行,每行一个整数,表示数列A_i。
输出格式 Output Format
一个整数,表示最大的价值之和。
算法分析:
设在区间[i,j]按照题目要求取数所获得的最大值为f(i,j),则
f(i,j) = max{f(i+1,j)+a[i]*(n+i-j),f(i,j-1)+a[i]*(n+i-j)}
f(i,i) = a[i]*n
代码:
#include <iostream>
#include <memory.h>
using namespace std;
const int maxn = 2010;
int a[maxn];
int f[maxn][maxn];
int n;
int dp(int i,int j)
{
if(f[i][j]!=-1) return f[i][j];
return f[i][j]=max(dp(i+1,j)+a[i]*(n+i-j),dp(i,j-1)+a[j]*(n+i-j));
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) f[i][i]=n*a[i];
cout<<dp(1,n)<<endl;
return 0;
}
分享到:
相关推荐
tyvj1126 1150测试数据 需要的下载…
tyvj关闭,无奈,自己用这个测好了,EasyTest 兼容此数据库。
这个是TYVJ题库的P1005:滑雪 问题的解 我采用了向四个方向搜索的办法 在其网站上的评测系统中通过
tyvj在线题库前一百道题(1000~1099)测试数据 经测试有效 好东西拿来与大家共享
tyvj上的部分题解,还有部分源码,poj上的水题
var s:string; i,l,cha,max,min:integer; x:char; panduan:boolean; chance:array['a'..'z']of integer; begin readln(s); l:=length(s); fillchar(chance,sizeof(chance),0); for i:=1 to l do ...end.
tyvj上的测试数据需要的下载。。。。。
TYVJ源代码 VIJOS 源代码 (一共五部分) 此部分只包含
TYVJ源代码 VIJOS源代码 此部分只包含题目 代码部分:http://download.csdn.net/download/a710128/7630117 一共五部分
TYVJ源代码 VIJOS 源代码 此部分只包含题目 代码在 http://download.csdn.net/download/a710128/7630117 一共五部分
TYVJ源代码 VIJOS 源代码 此部分只包含题目 代码部分 : http://download.csdn.net/download/a710128/7630117 一共五部分
Tyvj_p1048_田忌赛马1
TYVJ的代码。 题目请放在Problem文件夹里(因为比较大,我就不打包了,网上有现成的) http://dl.dbank.com/c0mhhdh9ec 这里可以下载
请不要再下载 ...。。。 那个有问题,现在我发一个新的 里面有一个教程(自认为写得很完整) 贴上后面几部分的地址(后面的不要分) ...如果有什么问题,请在 CSDN 上联系我
问题:输入一个长度为n的整数序列,从中找出一段不超过M的连续子序列,使得整个序列的和最大。 采用c#实现:求最大子序列的值。
vijos的本地版题库,收集了经典的300多道题
奥赛信息学在线评测网站快捷登陆。 包含TYVJ,WIKIOI等著名评测网站
为OIer一年以来写的代码 包括网站bzoj,cojs,tyvj,poj等题库代码
一套很好的OI题目。 下载自tyvj。 比赛时间:8.24晚。 难度NOIP。 前两题简单,最后一题很有趣。
重庆2012noip提高组day1所有选手的程序,只要你参加了noip2012重庆提高组,里面就有你的源程序,可以提交至tyvj测评估分!