校oj10532: 生成字符串（dp，最优状态转移）-白红宇

校oj10532: 生成字符串（dp，最优状态转移）

阅读量：4046 次

发布时间：2019-05-25

本文共 1171 字，大约阅读时间需要 3 分钟。

题目：

10532: 生成字符串

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 91 Solved: 5

[ ][ ][ ]

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

我竟然没看出来这是一道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
   
        #include
    
         #include
     
          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<
      
       <

转载地址：http://ouyci.baihongyu.com/

你可能感兴趣的文章