记录编号	2718	评测结果	AAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	2.502 s
提交时间	2008-09-25 12:42:11	内存使用	36.03 MiB

#include <iostream>
#include <string>
#define MAXP 201
#define LIM 1000000000
#define MAXW 9
//1000000000
using namespace std;

class hpnum
{
public:
	long sec[MAXP];
	int seccnt;
 
	hpnum()
	{
		sec[seccnt=1]=0;
	}
	bool bigger(hpnum &b)
	{
		if (seccnt>b.seccnt)
			return true;
		if (seccnt<b.seccnt)
			return false;
		int i;
		for (i=seccnt;i>=1;i--)
		{
			if (sec[i]>b.sec[i])
				return true;
			if (sec[i]<b.sec[i])
				return false;
		}
		return true;
	}
	void plus(hpnum &P)
	{
		int sect=seccnt>P.seccnt?seccnt:P.seccnt;
		long T,up=0;
		for(int i=1;i<=sect;i++)
		{
			if (i>seccnt)sec[i]=0;
			if (i>P.seccnt)P.sec[i]=0;
			T=sec[i]+P.sec[i]+up;
			up=T/LIM;
			sec[i]=T%LIM;
		}
		seccnt=sect;
		if (up)
			sec[++seccnt]=up;
	}
	void cpy(hpnum &P)
	{
		seccnt=P.seccnt;
		for (int i=1;i<=seccnt;i++)
			sec[i]=P.sec[i];
	}
	void conv(int V)
	{
		sec[seccnt=1]=0;
		int i=1;
		while (V)
		{
			sec[i]=V % LIM;
			V-=sec[i];
			V/=LIM;
			i++;
		}
		seccnt=i-1;
	}
	void print()
	{
		int i,k;
		for (i=seccnt;i>=1;i--)
		{
			k=LIM/10;
			if (i!=seccnt && sec[i]<k)
			{	
				while (sec[i]<k)
				{
					cout << 0;
					k/=10;
				}
			}
			if (sec[i])
				cout << sec[i];
		}
		if (sec[1]==0 && seccnt==1)
			cout << 0;
	}
	hpnum* operator=(int a)
	{
		conv(a);
		return this;
	}
	hpnum* operator=(hpnum a)
	{
		cpy(a);
		return this;
	}
};

hpnum operator+(hpnum a,hpnum &b)  
{
	a.plus(b);
	return a;   
}

bool operator>(hpnum &a,hpnum &b)  
{   
	return a.bigger(b);
}

typedef hpnum var;

string S;
int K,N;
var num[MAXP][MAXP],F[MAXP][30],INF;

void init()
{
	int i,j,k,l;
	string T;
	freopen("exam4.in","r",stdin);
	freopen("exam4.out","w",stdout);
	cin >> S >> K;
	N=S.length();
	K++;
	for (i=1;i<=N;i++)
	{
		for (j=i;j<=N;j++)
		{
			for (k=j-MAXW,l=1;k>=i;k-=MAXW,l++)
			{
				T=S.substr(k,MAXW);
				sscanf(T.c_str(),"%d",&num[i][j].sec[l]);
			}
			T=S.substr(i-1,k+MAXW-i+1);
			sscanf(T.c_str(),"%d",&num[i][j].sec[l]);
			num[i][j].seccnt=l;
			/*printf("F[%d][%d] = ",i,j);
			num[i][j].print();
			cout << endl;*/
		}
	}
	for (i=1;i<MAXP;i++)
		INF.sec[i]=9;
	INF.seccnt=MAXP;
}

void dynamic()
{
	int i,j,k;
	var min,p;
	for (i=1;i<=N;i++)
		F[i][1]=num[1][i];
	for (j=2;j<=K;j++)
	{
		for (i=1;i<=N;i++)
		{
			if (j>i) continue;
			min=INF;
			for (k=1;k<=i-1;k++)
			{
				if (j-1>k) continue;
				p=F[k][j-1]+num[k+1][i];
				if (min>p)
					min=p;
			}
			F[i][j]=min;
		}
	}
	F[N][K].print();
}

int main()
{
	init();
	dynamic();
	return 0;
}