動態規劃練習題：填加號 解題報告

【問題描述】
有一個由數字 1 ， 2 ， … ， 9 組成的數字串（長度不超過 200 ），問如何將 M(M<=20) 個加號 (“+”) 插入到這個數字串中，使所形成的算術表達式的值最小。請編一個程序解決這個問題。 注意： 加號不能加在數字串的最前面或最末尾，也不應有兩個或兩個以上的加號相鄰。 M 保證小於數字串的長度。 例如：數字串 79846 ，若需要加入兩個加號，則最佳方案為 79+8+46 ，算術表達式的值 133 。
【輸入格式】
數字串在輸入文件的第一行行首（數字串中間無空格且不折行），Ｍ的值在輸入文件的第二行行首。
【輸出格式】
輸出所求得的最小和的精確值。
【輸入輸出樣例】

輸入：
exam4.in
82363983742
3
輸出：
exam4.out
2170

【分析】
動態規劃，類似於『NOIP2000 乘積最大』。
狀態設定：
F[i,j] ：前i個數添加j個乘號的最小和
Num[i,j]：原數中第i個數到第j個數組成的新數。
邊界狀態：F[i,0]=Num[1,i]
狀態轉移方程： F[i,j]=Min{F[k,j-1]+Num[k+1,i]}
目標狀態：F[N,K]
由於數據比較大，所以需要高精度計算。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int SIZE=201;
int K;
int N;
typedef unsigned short int usint;
struct hugeint
{
 usint len,num[SIZE];
};
hugeint Num[201][201];
hugeint F[201][21];
void print(hugeint a)
{
 int i;
 for (i=a.len;i>=1;i--)
  printf("%d",a.num[i]);
 printf("\n");
}
hugeint add(hugeint a,hugeint b)
{
 int i;
 hugeint ans;
 memset(ans.num,0,sizeof(ans.num));
 if (a.len>b.len)
  ans.len=a.len;
 else
  ans.len=b.len;
 for (i=1;i<=ans.len;i++)
 {
  ans.num[i]+=(a.num[i]+b.num[i]);
  ans.num[i+1]+=ans.num[i]/10;
  ans.num[i]%=10;
 }
 if (ans.num[ans.len+1]>0)
  ans.len++;
 return ans;
}
bool over(hugeint a,hugeint b)
{
 int i;
 if (a.len<b.len)
  return false;
 if (a.len>b.len)
  return true;
 for (i=a.len;i>=1;i--)
 {
  if (a.num[i]<b.num[i])
   return false;
  if (a.num[i]>b.num[i])
   return true;
 }
 return false;
}
void init()
{
 hugeint tmp;
 memset(tmp.num,0,sizeof(tmp.num));
 char str[201];
 scanf("%s\n%d\n",&str,&K);
 int len=strlen(str);
 tmp.len=len;
 N=len;
 for (int i=0;i<len;i++)
 {
  tmp.num[i+1]=str[i]-'0';
 }
 for (int i=1;i<=len;i++)
 {
  for (int j=i;j<=len;j++)
  {
   memset(Num[i][j].num,0,sizeof(Num[i][j].num));
   Num[i][j].len=j-i+1;
   int top=Num[i][j].len;
   for (int k=i;k<=j;k++)
   {
    Num[i][j].num[top]=tmp.num[k];
    top--;
   }
   /*
   printf("%d %d %d ",i,j,Num[i][j].len);
   print(Num[i][j]);
   */
  }
 }
}
void dynamic()
{
 for (int i=1;i<=N;i++)
  F[i][0]=Num[1][i];
 for (int j=1;j<=K;j++)
 {
  for (int i=1;i<=N;i++)
  {
   for (int k=1;k<=N;k++)
    F[i][j].num[k]=9;
   F[i][j].len=N;
   for (int k=1;k<=i-1;k++)
   {
    hugeint temp=add(F[k][j-1],Num[k+1][i]);
    if(over(F[i][j],temp) )
    {
     F[i][j]=temp;
    }
   }
  }
 }
 print(F[N][K]);
}
int main()
{
 freopen("exam4.in","r",stdin);
 freopen("exam4.out","w",stdout);
 init();
 dynamic();
 return 0;
}