codeforces 710E E. Generate a String(dp)
题目链接:
2 seconds
512 megabytes
standard input
standard output
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.
8 1 1
4
8 1 10
8 题意: 现在添加一个或者删除一个a需要x,复制一次需要y,问正好有n个a至少需要多少时间; 思路: dp[i]表示正好i个a需要的最少时间,i为偶数的时候dp[i]=min{dp[i-1]+x,dp[i+1]+x,dp[i/2]+y}
i为奇数的时候dp[i]=min{dp[i-1]+x,dp[i+1]+x};
这样写的状态转移方程没法转移啊,把这些式子组合考虑一下可以知道:
当确定了i的dp[i]的时候,可以得到dp[i*2]的估计值为dp[i]+y;这就是得到了偶数的估计值,
所以i%2==1时dp[i]=min{dp[i-1]+x,dp[i+1]+x};i%2==0时dp[i]=min{dp[i-1]+x,dp[i/2]+y}; AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <stack>
#include <map> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
if(!p) { puts("0"); return; }
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('\n');
} const LL mod=1e9+7;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=2e7+10;
const int maxn=1e3+20;
const double eps=1e-12; LL dp[N],x,y;
int n;
int main()
{ read(n);read(x);read(y);
dp[1]=x;dp[2]=x+y;
for(int i=2;i<=n;i++)
{
if(i&1)dp[i]=min(dp[i-1]+x,dp[i+1]+x);
else dp[i]=min(dp[i-1]+x,dp[i/2]+y);
dp[2*i]=dp[i]+y;
}
cout<<dp[n]<<endl;
return 0;
}
最新文章
- 搭建web框架手册(一)
- Codeforces Round #371 (Div. 2) C
- js-JavaScript高级程序设计学习笔记13
- IOS 网络浅析-(六 网络图片获取之三方SDWebImage)
- mysql字段额外属性,除去字段类型外的其他属性
- Pentium II paging mechanism
- 【Origin】答友朋关切书
- js的相关验证
- [LeetCode]题解(python):095-Unique Binary Search Trees II
- 部分PC端安卓管理器使用强行断开重连的方法来连接手机,容易丢书数据,损坏数据
- Android替换APP字体 — Typeface
- redis的删除库应用(linux)
- nginx+tomcat+session共享(转)
- [USACO12JAN]爬山Mountain Climbing
- Win32线程安全问题.同步函数
- Thinkphp3.2+PHPQRCode 二维码生成示例
- 珍藏40个android应用源码分享
- nw.js node-webkit系列(15)如何使用内部模块和第三方模块进行开发
- SSL虚拟主机安全方案
- Spring-导入和混合配置