首页 > 代码库 > bzoj1652[Usaco2006 Feb]Treats for the Cows*

bzoj1652[Usaco2006 Feb]Treats for the Cows*

bzoj1652[Usaco2006 Feb]Treats for the Cows

题意:

管子里n个巧克力,第i个价值为ai。每天从左端点或右端点拿一个出来卖,收入为这个巧克力的价值*它是第几天卖出的。问最大价值。n≤2000

题解:

dp:f[l][r]=max(f[l+1][r]+a[l]*(n-(r-l+1)+1),f[l][r-1]+a[r]*(n-(r-l+1)+1))。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 2010
 7 #define ll long long
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<0||ch>9){if(ch==-)f=-1; ch=getchar();}
13     while(ch>=0&&ch<=9)x=x*10+ch-0,ch=getchar();
14     return f*x;
15 }
16 ll f[maxn][maxn]; int a[maxn],n;
17 ll dfs(int l,int r){
18     if(l>r)return 0; if(f[l][r]!=-1)return f[l][r];
19     f[l][r]=max(dfs(l+1,r)+a[l]*(n-(r-l)),dfs(l,r-1)+a[r]*(n-(r-l)));
20     return f[l][r];
21 }
22 int main(){
23     n=read(); inc(i,1,n)a[i]=read(); memset(f,-1,sizeof(f));
24     printf("%lld",dfs(1,n)); return 0;
25 }

 

20160929

bzoj1652[Usaco2006 Feb]Treats for the Cows*