首页 > 代码库 > 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*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。