打卡信奥刷题（2939）用C++实现信奥题 P5810 [SCOI2004] 文本的输入

P5810 [SCOI2004] 文本的输入

题目描述

人们在输入文本时，除了逐个输入这种方式外，还可以利用剪贴板进行复制，如果打入一个字母需要111的时间，将已输入的部分复制进剪贴板需要555的时间（Ctrl+A，Ctrl+C，再取消全选状态），将剪贴板的内容粘贴出来需要222的时间（Ctrl+V）。

如果我们不关心输入文本的内容，而只关心输入文本的长度，要输入一个长度不低于nnn的文本最少需要多少时间？

请注意，数据范围与原题略有不同。

输入格式

一个正整数nnn，表示文本的长度。

输出格式

一个正整数ttt，表示需要的最短的时间。

输入输出样例 #1

输入 #1

20

输出 #1

16

说明/提示

样例解释：先用777时间打出777个字符，再复制（用去555时间），粘贴两次（用去444时间），即可用161616时间打出212121个字符。

对于20%20\%20%的数据，n≤10n\le 10n≤10；

对于60%60\%60%的数据，n≤104n\le 10^4n≤104；

对于100%100\%100%的数据，n≤4×104n\le 4\times 10^4n≤4×104。

C++实现

#include<cstdio>usingnamespacestd;constintmax_n=120;intdp[max_n]={};intmain(){intn,ans;scanf("%d",&n);if(n==0){puts("0");return0;}for(ans=1;dp[ans-1]<n;ans++){dp[ans]=dp[ans-1]+1;for(inti=ans-7,j=2;i>0;i-=2,j++)if(dp[ans]<dp[i]*j)dp[ans]=dp[i]*j;}printf("%d\n",ans-1);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容