北郵校賽的H題。
一開始亂搞，WA了，後來DP了一下，分四種情況就可以。
[cpp]
#include <iostream>
#define inf 1<<28
using namespace std;
int a[3000];
int main()
{
int T;
for (int i = 0 ;i <= 2222; i ++)a[i] = inf ;
a[1] = 1;a[2] = 2 ;a[3] = 3;a[4] = 4;a[5] = 5;a[6] = 5;a[7] = 6;a[8] = 6;a[9] = 6;//手算的初值
for (int i = 9 ;i <= 2005 ;i ++)
{
for (int j = i - 1 ;j >= 1; j --)
{
int t1 = i/j;//復制的次數
int t2 = i%j;//加的次數
a[i] = min(a[i],t1 - 1 + t2 + 1 + a[j]);//復制
a[i] = min(a[i], a[j] + i - j);//加
a[i - 1 ] = min(a[i - 1], a[i] + 1);//刪除
}
for (int j = i + 1 ;j <= 2005 ;j ++)
a[j] = min(a[j] , a[j- 1 ] + 1);//後一位加一
}
int d;
while(cin >> d)
cout <<a[d]<<endl;
return 0;
}
#include <iostream>
#define inf 1<<28
using namespace std;
int a[3000];
int main()
{
int T;
for (int i = 0 ;i <= 2222; i ++)a[i] = inf ;
a[1] = 1;a[2] = 2 ;a[3] = 3;a[4] = 4;a[5] = 5;a[6] = 5;a[7] = 6;a[8] = 6;a[9] = 6;//手算的初值
for (int i = 9 ;i <= 2005 ;i ++)
{
for (int j = i - 1 ;j >= 1; j --)
{
int t1 = i/j;//復制的次數
int t2 = i%j;//加的次數
a[i] = min(a[i],t1 - 1 + t2 + 1 + a[j]);//復制
a[i] = min(a[i], a[j] + i - j);//加
a[i - 1 ] = min(a[i - 1], a[i] + 1);//刪除
}
for (int j = i + 1 ;j <= 2005 ;j ++)
a[j] = min(a[j] , a[j- 1 ] + 1);//後一位加一
}
int d;
while(cin >> d)
cout <<a[d]<<endl;
return 0;
}
