Educational Codeforces Round 16 E. Generate a String dp
题目链接:
http://codeforces.com/problemset/problem/710/E
E. Generate a String
time limit per test 2 secondsmemory limit per test 512 megabytes
#### 问题描述
> zscoder wants to generate an input file for some programming competition problem.
>
> His input is a string consisting of n letters 'a'. He is too lazy to write a generator so he will manually generate the input in a text editor.
>
> Initially, the text editor is empty. It takes him x seconds to insert or delete a letter 'a' from the text file and y seconds to copy the contents of the entire text file, and duplicate it.
>
> zscoder wants to find the minimum amount of time needed for him to create the input file of exactly n letters 'a'. Help him to determine the amount of time needed to generate the input.
#### 输入
> The only line contains three integers n, x and y (1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109) — the number of letters 'a' in the input file and the parameters from the problem statement.
#### 输出
> Print the only integer t — the minimum amount of time needed to generate the input file.
#### 样例
> **sample input**
> 8 1 1
>
> **sample output**
> 4
题意
加减1的消耗是x,乘2的消耗是y,问通过这三个操作把0变成n的最小消耗
题解
贪心+dp
能证明的是偶数都不可能由后面的减回来的,所以即使是奇数也只能由后面的那个偶数减回来,而那个偶数就不用考虑后面再减了。
所以有转移方程:
i是偶数: dp[i]=min(dp[i/2]+y,dp[i-1]+x)
i是奇数: dp[i]=min(dp[i/2+1]+x+y,dp[i-1]+x)
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=1e7+10;
LL dp[maxn];
int n,x,y;
int main() {
scf("%d%d%d",&n,&x,&y);
dp[1]=x;
for(int i=2;i<=n;i++){
if(i&1){
dp[i]=min(dp[i-1]+x,dp[i/2+1]+y+x);
}else{
dp[i]=min(dp[i/2]+y,dp[i-1]+x);
}
}
prf("%I64d\n",dp[n]);
return 0;
}
//end-----------------------------------------------------------------------
划分阶段,然后先处理乘2,再处理乘加,再处理乘减。(但是感觉还是在偶数不可能通过更大的数减回来的这个结论的基础上做的,可能没有理解清楚吧。。)
阶段1:1~2(dp[1]=x,dp[2]=min(x,y))
阶段2:2~4
...
阶段m:n~n*2
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef __int64 LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=2e7+10;
LL dp[maxn];
int n,x,y;
int main() {
clr(dp,0x3f);
scf("%d%d%d",&n,&x,&y);
dp[1]=x;
dp[2]=min(x+dp[1],y+dp[1]);
for(int cur=2;cur<=n;cur<<=1){
for(int i=cur;i<=cur*2;i++){
if(i%2==0) dp[i]=min(dp[i],dp[i/2]+y);
dp[i]=min(dp[i],dp[i-1]+x);
}
for(int i=cur*2;i>=cur;i--){
dp[i]=min(dp[i],dp[i+1]+x);
}
}
prf("%I64d\n",dp[n]);
return 0;
}
//end-----------------------------------------------------------------------
最新文章
- MySQL Error Handling in Stored Procedures
- gitHub-初识
- shell 数学计算
- Spring 注解 @Resource和@Autowired(转)
- !a &;&; !b 和 !(a || b) 的故事
- scikit-learn的主要模块和基本使用
- Android学习之 AChartEngine 图表绘制
- Android相机是如何获取到图像的
- mongodb 3.4 集群搭建:分片+副本集
- redis 写入的时候报错
- HTML5无刷新修改Url,history pushState/replaceState
- 用Itextsharp 组件导出PDF 的文档的方法
- C# 绘制圆角矩形
- java-启动和关闭.exe程序
- 自动化测试 | UI Automator 入门指南
- HDU-6440-费马小定理
- Linux学习之用户管理命令与用户组管理命令(十五)
- Tcp端口以及端口相关协议详解
- es高级部分
- WAP用户评论简单实现瀑布流加载