Little Sub and Piggybank (杭师大第十二届校赛G题) DP

时间:2022-06-26 09:09:14

题目传送门

题意:每天能往存钱罐加任意实数的钱,每天不能多于起那一天放的钱数。如果某一天的钱数恰好等于那天的特价商品,则可以买,求最后的最大快乐值。

思路:先来一段来自出题人的题解:

  显然的贪心:如果第$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的更多相关文章

  1. Little Sub and Traveling(杭师大第十二届校赛E题) 欧拉回路

    题目传送门 题目大意: 从0出发,每次只能跳到(i*2)%n或者(i*2+1)%n,求字典序最大的哈密顿回路. 思路: 首先n为奇数时无解,先来证明这一点. 先假设n为奇数,若要回到原点,则必定有一步 ...

  2. HZNU第十二届校赛赛后补题

    愉快的校赛翻皮水! 题解 A 温暖的签到,注意用gets #include <map> #include <set> #include <ctime> #inclu ...

  3. 第十二届湖南省赛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 ...

  4. 福建工程学院第十四届ACM校赛G题题解

    外传:编剧说了不玩游戏不行 题意: 有n个石堆,我每次只能从某一堆中取偶数个石子,你取奇数个,我先手,先不能操作的人输.问最后谁能赢. 思路: 这个题仔细想想,就发现,取奇数的人有巨大的优势,因为假设 ...

  5. 台州学院第十二届校赛记录(B&comma;C&comma;E&comma;H&comma;I&comma;J&comma;L)

    传送门:点我 题目很棒,感谢出题验题的大佬们. 细节坑不少,是好事. 还是很菜,继续加油! B: 桃子的生日 时间限制(普通/Java):1000MS/3000MS     内存限制:65536KBy ...

  6. 湖南省第十二届省赛:Parenthesis

    Description Bobo has a balanced parenthesis sequence P=p1 p2…pn of length n and q questions. The i-t ...

  7. 福州大学第十届校赛 &amp&semi; fzu 2128最长子串

    思路: 对于每个子串,求出 母串中 所有该子串 的 开始和结束位置,保存在 mark数组中,求完所有子串后,对mark数组按 结束位置排序,然后 用后一个的结束位置 减去 前一个的 开始 位置 再 减 ...

  8. 第十二届湖南省赛 (B - 有向无环图 )(拓扑排序&plus;思维)好题

    Bobo 有一个 n 个点,m 条边的有向无环图(即对于任意点 v,不存在从点 v 开始.点 v 结束的路径). 为了方便,点用 1,2,…,n 编号. 设 count(x,y) 表示点 x 到点 y ...

  9. 第十二届湖南省赛 A - 2016 ( 数学,同余转换)

    给出正整数 n 和 m,统计满足以下条件的正整数对 (a,b) 的数量:       1. 1≤a≤n,1≤b≤m;   2. a×b 是 2016 的倍数.   Input   输入包含不超过 30 ...

随机推荐

  1. spark1&period;3编译过程中遇到的一个坑

    在编译spark1.3.0时: export MAVEN_OPTS="-Xmx2g -XX:MaxPermSize=512M -XX:ReservedCodeCacheSize=512m&q ...

  2. Atitit&period;电脑图片与拍摄图片的分别

    Atitit.电脑图片与拍摄图片的分别 1. Extname都是jpg的..1 1.1. 数码照片的Exif信息, 1 1.2. 是否有人脸1 1.3. 是否skin图1 1.4. 是否大面积色素单一 ...

  3. 【LeetCode】8&period; String to Integer &lpar;atoi&rpar; 字符串转整数

    题目: Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input ca ...

  4. C&num; 分页

    #region 分页 /// <summary> /// 分页 /// </summary> /// <param name="page">当前 ...

  5. Akka&period;net开发第一个分布式应用

    Akka.net开发第一个分布式应用 系列主题:基于消息的软件架构模型演变 既然这个系列的主题是”基于消息的架构模型演变“,少不了说说Actor模型.Akka.net是一个基于Actor模型的分布式框 ...

  6. Razor视图

    @{ string name="jerry";} <div> @name </div>     //显示jerry @{ string js="& ...

  7. Vue&period;js——60分钟组件快速入门

    一.组件简介 组件系统是Vue.js其中一个重要的概念,它提供了一种抽象,让我们可以使用独立可复用的小组件来构建大型应用,任意类型的应用界面都可以抽象为一个组件树: 那么什么是组件呢?组件可以扩展HT ...

  8. 比较ASP&period;NET和ASP&period;NET Core&lbrack;经典 Asp&period;Net v和 Asp&period;Net Core &lpar;Asp&period;Net Core MVC&rpar;&rsqb;

    ASP.NET Core是.与.Net Core FrameWork一起发布的ASP.NET 新版本,最初被称为ASP.NET vNext,有一系列的命名变化,ASP.NET 5.0,ASP.NET ...

  9. Ionic3 新增 Service

    service是单例模式的 新增Service类 search.service.ts import {Injectable} from '@angular/core'; @Injectable() e ...

  10. nginx重启命令

    service nginx restart nginx -s re