POJ 3186 Treats for the Cows (动态规划)
2024-09-01 05:58:21
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.
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
5
1
3
1
5
2
Sample Output
43 题意:
可以从数组的左右两端拿数字,权值依次上升,求权值乘上数字的和的最大值。
思路:
dp[i][j]表示起点为i,终点为j的组数,可以得到的最大值是多少。
首先枚举长度,再计算该长度所有的dp[i][j]的值。
代码:
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#define fuck(x) cout<<#x<<" = "<<x<<endl;
#define ls (t<<1)
#define rs ((t<<1)+1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = ;
const int inf = 2.1e9;
const ll Inf = ;
const int mod = ;
const double eps = 1e-;
const double pi = acos(-);
int num[];
int dp[][];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&num[i]);
}
for(int i=;i<=n;i++){
dp[i][i]=num[i]*n;
}
for(int len=;len<=n;len++){
for(int i=;i<=n;i++){
int j=i+len-;
if(j<=n)dp[i][j]=max(dp[i][j],dp[i][j-]+num[j]*(n-len+));
j=i-len+;
if(j>=)dp[j][i]=max(dp[j][i],dp[j+][i]+num[j]*(n-len+));
}
}
printf("%d\n",dp[][n]);
return ;
}
最新文章
- js和jquery常用方法
- System.TypeInitializationException: The type initializer for &#39;Mono.Unix.Native.Stdlib&#39; threw an exception.
- [转载] YouCompleteMe
- 网络请求时 返回 App Transport Security has blocked a cleartext HTTP
- hadoop hdfs 一些命令记录
- 搭建自己的Git服务器
- JsonArray和JsonObject遍历方法
- Tiny4412之按键驱动
- [LeetCode] Possible Bipartition 可能的二分图
- linux命令技巧
- kruskal(拓展)
- Mybatis核心配置文件SqlMapConfig.xml
- luoguP4707 重返现世
- Rabbitmq(7) confirm模式
- MySQL--事务隔离级别RR和RC的异同
- unity中让摄像机移动到鼠标点击的位置和鼠标控制平移视角
- Oracle的sys和system默认密码
- Python 四种数值类型(int,long,float,complex)区别及转换
- Material Design系列第一篇——Creating Apps with Material Design
- 也谈SpringCloud:假如 《复仇者联盟4》是一个微服务
热门文章
- SQL Server 更新统计信息出现严重错误,应放弃任何可能产生的结果
- macos 远程 windows 10
- python ----面向对象的三大特性---多态
- Windows10系统无法更新
- Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization(一)
- 为什么不建议在 HBase 中使用过多的列族
- velocity模板引擎 -- java.io.FileNotFoundException: velocity.log (Permission denied)
- Docker概述
- ASP.NET Core 微服务初探[1]:服务发现之Consul
- python3 time模块