题意:每天能往存钱罐加任意实数的钱,每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品,则可以买,求最后的最大快乐值。
思路:先来一段来自出题人的题解:
显然的贪心:如果第$i$天买完,准备在第$j$天买,那么显然最优是在$i+1$到j天放$wi/(j-i)$的钱。 于是假定选择的物品是$k1,k2,k3… $那么必须满足:
$a[ki]/(ki-ki-1)<=a[ki-1]/(ki-1-ki-2)$
令$f[i][j]$表示最后购买的两个物品为i和j,则$f[i][j]=max(f[j][k]+v[i])$ (j->k->i合法) 观察到上述条件可以把k分离,即$k>=j-(i-j)*a[j]/a[i]$,因此可以维护前缀和来使得时间复杂度变为$O(n2)$。
这是来自zju的cjb学长的题解,接下来是我对这道题的一些理解。
$f[i][j]$最后一次买的是第i个物品,前一次是第j个物品的最大收益,那么我们就有$f[i][j]=max(f[j][k]+v[i])$并且i,j,k要合法,合法的条件就是$a[i]/(i-j)<=a[j]/(j-k)$,那么我们把这个式子移一下项,就得到了合法条件是$k>=j-(i-j)*a[j]/a[i]$,然后我们用$g[j][k]$表示,以k为起点,所有买了j物品的最大的f[j][k],即$g[j][k]=max(f[j][k])$,然后同时维护$f$和$g$两个结构就可以了。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
const int maxn=;
int n,f[maxn][maxn],g[maxn][maxn],ans,a[maxn],v[maxn],k;
int main(){
while(cin>>n)
{
for(int i=;i<=n;i++)
{
cin>>a[i];
}
for(int i=;i<=n;i++)
{
cin>>v[i];
}
clr(f,),clr(g,);
for(int i=;i<=n;i++)
{
f[i][]=v[i];
for(int j=;j<i;j++)
{
if(!a[i])k=;
else k=max(ceil(j-1.0*a[j]/a[i]*(i-j)),0.0);
if(j>=k&&g[j][k])
f[i][j]=max(f[i][j],g[j][k]+v[i]);
}
for(int j=i-;j>=;j--)
{
g[i][j]=max(g[i][j+],f[i][j]);
}
}
ans=;
rep(i,,n)ans=max(ans,g[i][]);
printf("%d\n",ans);
}
return ;
}
Little Sub and Piggybank (杭师大第十二届校赛G题) DP的更多相关文章
-
Little Sub and Traveling(杭师大第十二届校赛E题) 欧拉回路
题目传送门 题目大意: 从0出发,每次只能跳到(i*2)%n或者(i*2+1)%n,求字典序最大的哈密顿回路. 思路: 首先n为奇数时无解,先来证明这一点. 先假设n为奇数,若要回到原点,则必定有一步 ...
-
HZNU第十二届校赛赛后补题
愉快的校赛翻皮水! 题解 A 温暖的签到,注意用gets #include <map> #include <set> #include <ctime> #inclu ...
-
第十二届湖南省赛G - Parenthesis (树状数组维护)
Bobo has a balanced parenthesis sequence P=p 1 p 2…p n of length n and q questions. The i-th questio ...
-
福建工程学院第十四届ACM校赛G题题解
外传:编剧说了不玩游戏不行 题意: 有n个石堆,我每次只能从某一堆中取偶数个石子,你取奇数个,我先手,先不能操作的人输.问最后谁能赢. 思路: 这个题仔细想想,就发现,取奇数的人有巨大的优势,因为假设 ...
-
台州学院第十二届校赛记录(B,C,E,H,I,J,L)
传送门:点我 题目很棒,感谢出题验题的大佬们. 细节坑不少,是好事. 还是很菜,继续加油! B: 桃子的生日 时间限制(普通/Java):1000MS/3000MS 内存限制:65536KBy ...
-
湖南省第十二届省赛:Parenthesis
Description Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions. The i-t ...
-
福州大学第十届校赛 &; fzu 2128最长子串
思路: 对于每个子串,求出 母串中 所有该子串 的 开始和结束位置,保存在 mark数组中,求完所有子串后,对mark数组按 结束位置排序,然后 用后一个的结束位置 减去 前一个的 开始 位置 再 减 ...
-
第十二届湖南省赛 (B - 有向无环图 )(拓扑排序+思维)好题
Bobo 有一个 n 个点,m 条边的有向无环图(即对于任意点 v,不存在从点 v 开始.点 v 结束的路径). 为了方便,点用 1,2,…,n 编号. 设 count(x,y) 表示点 x 到点 y ...
-
第十二届湖南省赛 A - 2016 ( 数学,同余转换)
给出正整数 n 和 m,统计满足以下条件的正整数对 (a,b) 的数量: 1. 1≤a≤n,1≤b≤m; 2. a×b 是 2016 的倍数. Input 输入包含不超过 30 ...
随机推荐
-
spark1.3编译过程中遇到的一个坑
在编译spark1.3.0时: export MAVEN_OPTS="-Xmx2g -XX:MaxPermSize=512M -XX:ReservedCodeCacheSize=512m&q ...
-
Atitit.电脑图片与拍摄图片的分别
Atitit.电脑图片与拍摄图片的分别 1. Extname都是jpg的..1 1.1. 数码照片的Exif信息, 1 1.2. 是否有人脸1 1.3. 是否skin图1 1.4. 是否大面积色素单一 ...
-
【LeetCode】8. String to Integer (atoi) 字符串转整数
题目: Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input ca ...
-
C# 分页
#region 分页 /// <summary> /// 分页 /// </summary> /// <param name="page">当前 ...
-
Akka.net开发第一个分布式应用
Akka.net开发第一个分布式应用 系列主题:基于消息的软件架构模型演变 既然这个系列的主题是”基于消息的架构模型演变“,少不了说说Actor模型.Akka.net是一个基于Actor模型的分布式框 ...
-
Razor视图
@{ string name="jerry";} <div> @name </div> //显示jerry @{ string js="& ...
-
Vue.js——60分钟组件快速入门
一.组件简介 组件系统是Vue.js其中一个重要的概念,它提供了一种抽象,让我们可以使用独立可复用的小组件来构建大型应用,任意类型的应用界面都可以抽象为一个组件树: 那么什么是组件呢?组件可以扩展HT ...
-
比较ASP.NET和ASP.NET Core[经典 Asp.Net v和 Asp.Net Core (Asp.Net Core MVC)]
ASP.NET Core是.与.Net Core FrameWork一起发布的ASP.NET 新版本,最初被称为ASP.NET vNext,有一系列的命名变化,ASP.NET 5.0,ASP.NET ...
-
Ionic3 新增 Service
service是单例模式的 新增Service类 search.service.ts import {Injectable} from '@angular/core'; @Injectable() e ...
-
nginx重启命令
service nginx restart nginx -s re