记录编号	106601	评测结果	AAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2014-06-14 21:52:03	内存使用	2.02 MiB

#include <iostream>
#include <cstdio>
#include <cstring>

#define  maxl  201
#define  maxk  21

using namespace std ;

#define  LenghthBigint  100   //Bigint可存储的长度为 LenghthBigint*SizeBigint
#define  CarryBigint    10000 //进制 
#define  SizeBigint     4     //进制-1的位数 

struct Bigint{
	int Data[LenghthBigint];
	int Size;
	Bigint(){ Size = 1 ; memset(Data,0,sizeof (Data)); }
};

void PrintfBigint(Bigint a)
{
	printf("%d",a.Data[a.Size]) ;
	for (int i = a.Size-1 ; i > 0 ; i -- ) printf("%04d",a.Data[i]);// printf("% 0 SizeBigint d",a.Data[i]) ; 
}

Bigint ToBigint(const string s)
{
	Bigint x ;
	int len = s.size() ;
	for(int i = 0 ; i < len ; i ++ )
	{
		int p = (len-i-1) / SizeBigint + 1 ;
		x.Data[p] = 10*x.Data[p] + s[i] - '0' ;
	}
	x.Size = (len-1) / SizeBigint + 1 ;
	return x ;
}

Bigint Add(Bigint a,Bigint b)
{
	Bigint x ;
	int i = 1 , r = 0 ;
	while (i <= a.Size || i <= b.Size)
	{
		x.Data[i] = a.Data[i] + b.Data[i] + r ;
		r = x.Data[i] / CarryBigint ;
		x.Data[i] = x.Data[i] % CarryBigint ;
		i ++ ;
	}
	if (r > 0) x.Data[i] += r ;
	else i -- ;
	x.Size = i ;
	return x ;
}

Bigint Min(Bigint a,Bigint b)
{
	if (a.Size != b.Size) return a.Size < b.Size ? a : b ;
	else
	{
		for (int i = a.Size ; i > 0 ; i -- )
		{
			if (a.Data[i] != b.Data[i]) return a.Data[i] < b.Data[i] ? a : b ;
		}
	}
	return a ;
}

inline string qread()
{
	char ch ;
	string s = "";
	while (ch = getchar() , ch < '0' || ch > '9' ) ;//根据需要 
	while (s += ch , ch = getchar() , '0' <= ch && ch <= '9') ;
	return s ;
}

/*
状态转移方程：f[en][k] = min { f[br][k-1] + num[en-br+1][en] } ( 0 <= br < en , 0 <= k <= m ; 
即前 en 坐标的数字添加 k 个加号的最小值 = min { 前 br 坐标的数字添加 k-1 个加号的最小值 + 坐标 br+1 到 en 的数字 }
*/

string Data ;
int m ;
Bigint f[maxl][maxk] ;	//	f[en][k] :前 en 坐标的数字添加 k 个加号的最小值
Bigint n[maxl] ;		//	n[en]    :坐标 0 到 en 的数字值 
Bigint Maxnum;			//	初始化某些值为  MaxBigint 

int main()
{
	freopen("exam4.in" ,"r",stdin ) ;
	freopen("exam4.out","w",stdout) ;
	Data = qread() ; scanf("%d",&m) ;
	Maxnum.Size = 99 ;					// 即 300 多位的一个数 
	int len = Data.size() ;
	for (int en = 0 ; en < len ; en ++ )
	{
		n[0] = ToBigint(Data.substr(0,en+1)) ;
		f[en][0] = n[0] ;						//0 到 en 坐标的部分添 0 个加号 为坐标 0 到 en 的数字 
		for (int br = 0 ; br < en ; br ++ )		//br 为前面某一部分的末端字符的坐标 
		{
			n[br+1] = ToBigint(Data.substr(br+1,en-br)) ;
			int k = m ;	if (k > br+1) k = br+1 ;
			for ( ; k > 0 ; k -- )
			{
				if(f[en][k].Data[1]==0) f[en][k] = Maxnum ; //如果还没有更新过这个值，将它赋值为 MaxBigint 
				Bigint t = Add(f[br][k-1] , n[br+1]) ;
				f[en][k] = Min(f[en][k] , t ) ;
			}
		}
	}
	PrintfBigint(f[len-1][m]) ;
	return 0;
}