【BZOJ】1652: [Usaco2006 Feb]Treats for the Cows(dp)
http://www.lydsy.com/JudgeOnline/problem.php?id=1652
dp。。
我们按间隔的时间分状态k,分别为1~n天
那么每对间隔为k的i和j。而我们假设i或者j在间隔时间内最后取。那么在这个间隔时间内最后取的时间就是n-k+1(这个自己想。。也就是说,之前在n-(k-1)+1的时间间隔内取过了,现在我们要多了一个时刻,相当于取这个早了一个时间)
然后就是
k为阶段
i为左端点
j=i+k-1为右端点
t=n-k+1为i-j取最后一个的时间
然后转移
f[i][j]=max(f[i+1][j]+t*a[i], f[i][j-1]+t*a[j])
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> #include <queue> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) #define for1(i,a,n) for(int i=(a);i<=(n);++i) #define for2(i,a,n) for(int i=(a);i<(n);++i) #define for3(i,a,n) for(int i=(a);i>=(n);--i) #define for4(i,a,n) for(int i=(a);i>(n);--i) #define CC(i,a) memset(i,a,sizeof(i)) #define read(a) a=getint() #define print(a) printf("%d", a) #define dbg(x) cout << #x << " = " << x << endl #define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; } inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } inline const int max(const int &a, const int &b) { return a>b?a:b; } inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=2005; int f[N][N], n, a[N]; int main() { read(n); for1(i, 1, n) read(a[i]); for1(k, 1, n) for(int i=1; i+k-1<=n; ++i) { int t=n-k+1, j=i+k-1; f[i][j]=max(f[i+1][j]+t*a[i], f[i][j-1]+t*a[j]); } print(f[1][n]); return 0; }
Description
FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time. The treats are interesting for many reasons: * The treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats. * Like fine wines and delicious cheeses, the treats improve with age and command greater prices. * The treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 <= v(i) <= 1000). * Cows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a. Given the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally? The first treat is sold on day 1 and has age a=1. Each subsequent day increases the age by 1.
约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了N(1≤N≤2000)份美味的零食来卖给奶牛们.每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:
Input
* Line 1: A single integer,
N * Lines 2..N+1: Line i+1 contains the value of treat v(i)
Output
* Line 1: The maximum revenue FJ can achieve by selling the treats
Sample Input
1
3
1
5
2
Five treats. On the first day FJ can sell either treat #1 (value 1) or
treat #5 (value 2).
Sample Output
OUTPUT DETAILS:
FJ sells the treats (values 1, 3, 1, 5, 2) in the following order
of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 = 43.
HINT
Source
相关文章
- Web Api调用遇到错误提示System.Web.HttpException (0x80004005): The controller for path '' was not found or does not implement IController.
- What is the _references.js used for?
- What's the replacement for fuslogvw in .net core 2?
- The ORDER BY clause is invalid in views, inline functions, derived tables, subqueries, and common table expressions, unless TOP or FOR XML is also specified.
- guidelines for contributing Hearthstone-Deck-Tracker
- Aspose.Words for .NET使用教程(一):基本介绍
- There is insufficient memory for the Java Runtime Environment to continue问题解决
- .Net Core 控制台程序错误:Can not find runtime target for framework '.NETCoreApp,Version=v1.0' compatible with one of the target runtimes: 'win10-x64, win81-x64, win8-x64, win7-x64'.
- Distributed systems theory for the distributed systems engineer
- CodeForcesGym 100641B A Cure for the Common Code
- Can't create a new thread (errno 11); if you are not out of available memory, you can consult the manual for a possible OS-dependent bug
- JRebel for IntelliJ 热部署破解方法
- The GuidRepresentation for the reader is CSharpLegacy, which requires the binary sub type to be Uuid
- SAP RETAIL The same code for Site Master & BP & Customer
- MySQL 5.6 中的 TIMESTAMP 和 explicit_defaults_for_timestamp 参数
- this class is not key value coding-compliant for the key XXX错误的解决方法
- Announcing the Updated NGINX and NGINX Plus Plug‑In for New Relic (Version 2)
- JS之for循环面试题
- ROCK : A Robust Clustering Algorithm for Categorical Attributes
- Skype for TV停止支持 三星确认今年6月移除该应用
- arcgis api 3.x for js 共享干货系列之一自写算法实现地图量算工具(附源码下载)
- Arcgis for Javascript实现图
- Program for Linux USB-devices driver step by step (ONE)
- Job for iptables.service failed because the control process exit with error code 修复
- Bash For Loop Examples for Your Linux Shell Scripting--ref
- Job for httpd.service failed because the control process exited with error code.
- 《RAFT:Recurrent All-Pairs Field Transforms for Optical Flow》论文笔记
- 《Inception V3-Rethinking the Inception Architecture for Computer Vision》论文笔记
- 《HRNet-OCR:Object-Contextual Representations for Semantic Segmentation》论文笔记
- 《To prune, or not to prune:exploring the efficacy of pruning for model compression》论文笔记
- windows安装dcm4chee 出错 check file system group LOSSY_STORAGE for deletion