3160675_tle.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int from[257][100000];
char dp[257][100000];
int add[257][100000];
int num;

int getnum(char str[],int st,int ed)
{
	char ch;
	int ret;

	ch = str[ed];
	str[ed] = 0;
	ret = atoi(&str[st]);
	str[ed] = ch;
	return ret;
}

int main()
{
	char str[300], ch;
	int tt;
	int i, j, m, l, k, t, len;
	int pos[300], cnt, nn, ed;

	//freopen("d.in","r",stdin);
	//freopen("d.out","w",stdout);
	k = 1;
	while(scanf("%s",str)==1)
	{
		if(strlen(str)>256)
			while(1)
				puts("i love sql");
		if(strcmp(str,"0=0")==0)
			break;
		printf("%d. ",k++);
		if(str[0]=='0')
		{
			puts("IMPOSSIBLE");
			continue;
		}
		for(l = 0; str[l]!='='; l++);
		num = atoi(&str[l+1]);
		//if(num >= 100000)
		//	while(1)
		//		puts("i love sql");
		len = strlen(&str[l+1]);
		//if(len > 5)
		//	while(1)
		//		puts("i love sql");
		for(i = 0; i <= l; i++)
		{
			for(j = 0; j <= num; j++)
			{
				dp[i][j] = 0;
				add[i][j] = -1;
			}
		}
		dp[0][0] = 1;
		pos[0] = -1;
		add[0][0] = 0;
		for(i = 1; i <= l; i++)
		{
			t = i-len+1;
			ch = str[i];
			str[i] = 0;
			if(t < 1)
				t = 1;
			for(j = t; j <= i; j++)
			{
				if(str[j-1]=='0')
					continue;
				tt = atoi(&str[j-1]);
				for(m = 0; m + tt <= num; m++)
				{
					if(dp[j-1][m]==1)
					{
						if(add[i][m+tt]==-1||add[i][m+tt]>add[j-1][m]+1)
						{
							add[i][m+tt] = add[j-1][m]+1;
							from[i][m+tt] = j-1;
						}
						dp[i][m+tt] = 1;
					}
				}
			}
			str[i] = ch;
		}
		if(dp[l][num]==1)
		{
			ed = l+1;
			nn = num;
			len = l;
			cnt = 0;
			memset(pos,0,sizeof(pos));
			while(1)
			{
				t = from[len][nn];
				tt = getnum(str,t,len);
				if(t==0)
					break;
				pos[t] = 1;
				nn -= tt;
				len = t;
			}
			for(i = 0; str[i]!='='; i++)
			{
				if(pos[i])
					putchar('+');
				putchar(str[i]);
			}
			puts(&str[l]);
		}
		else
			puts("IMPOSSIBLE");
	}
	return 0;
}