题目：
10532: 生成字符串
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 91 Solved: 5
[ Submit][ Status][ Web Board]
Description
Flowersea想为某些编程竞赛生成一个输入文件。
他的输入是由n个字母“a”组成的字符串。他懒得写一个生成器，所以他会在文本编辑器中手动输入生成。
最初，文本编辑器是空的。他需要花费x秒时间在文本文件中插入或删除一个字母“a”，或者在y秒内复制整个文本文件的内容，并粘贴它。
Flowersea希望找到创建正好n个字母“a”的输入文件所需的最少时间。请帮助他确定生成输入所需的时间。
Input
第一行一个整数T —— 表示有T组数据。
第二行包含三个整数n，x和y（1 ≤ n ≤ 10^7，1 ≤ x，y ≤ 10^9）—— 文件中字母“a”的个数，插入或删除所需的时间，拷贝一次所需要的时间。
Output
对于每组数据，输出一个整数t —— 生成输入文件所需的最小时间。
Sample Input
18 1 1
Sample Output
4
我竟然没看出来这是一道dp题。
分析：一开始我的思路很混乱，一直卡啥时候用复制呀，假设输入6个的话，会不会先输入4个，再复制两个？真是脑子进水，复制的时间都比输入两个的短了，当然可以复制三个了呀。
i为奇数。dp[i]=min(min(dp[i-1]+x,dp[i/2]+y+x),dp[(i+1)/2]+x+y); //直接输入一个，复制一下再输入，复制一下再删除
i为偶数。dp[i]=min(dp[i-1]+x,dp[i/2]+y);//直接输入，复制。
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int maxn=1e7+10;long longf dp[maxn];int main(){ int T;cin>>T;long n,x,y;while(T--){cin>>n>>x>>y;dp[1]=x;for(int i=2;i<=n;i++)if(i%2==1)dp[i]=min(min(dp[i-1]+x,dp[i/2]+y+x),dp[(i+1)/2]+x+y);else dp[i]=min(dp[i-1]+x,dp[i/2]+y);cout<<dp[n]<<endl;}}