3161426_ac_1782ms_41756k.cc

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

#include <stdio.h>
#include <vector>

using namespace std;

struct node
{
	int value;
	int num_of_plus;
	int prev;
};

vector <node> dp[257];
int value[5000000];
int prev[5000000];
int plus[5000000];
int maxvalue[257];
int minvalue[257];

int calc(char exp[])
{
	int l, i, tt;
	char ch;

	tt = 0;
	l = strlen(exp);
	for(i = l-5; i >= 0; i-=5)
	{
		ch = exp[i+5];
		exp[i+5] = 0;
		tt += atoi(&exp[i]);
		exp[i+5] = ch;
	}
	ch = exp[i+5];
	exp[i+5] = 0;
	tt += atoi(exp);
	exp[i+5] = ch;
	return tt;
}

int getnum(char exp[],int ed)
{
	char ch = exp[ed];
	exp[ed] = 0;
	int ret = atoi(exp);
	exp[ed] = ch;
	return ret;
}

void init(char exp[])
{
	int i, l;

	l = strlen(exp);
	minvalue[l] = 0;
	for(i = l-1; i >= 0; i--)
	{
		maxvalue[i] = calc(&exp[i]);
		minvalue[i] = minvalue[i+1]+(exp[i]-'0');
	}
}

int find_in_dp(int i,int num)
{
	int min, max, mid;

	min = 0;
	max = dp[i].size()-1;
	while(min <= max)
	{
		mid = (min+max)>>1;
		if(dp[i][mid].value == num)
			return mid;
		else
			if(dp[i][mid].value < num)
				min = mid+1;
			else
				max = mid-1;
	}
	return -1;
}

int main()
{
	node tmp;
	char exp[257];
	int cas, num, len;
	int i, j, p, t, l, it;

	cas = 1;
	while(scanf("%s",exp)==1)
	{
		if(strcmp(exp,"0=0")==0)
		{
			break;
		}
		dp[0].clear();
		tmp.num_of_plus = 0;
		tmp.prev = -1;
		tmp.value = 0;
		dp[0].push_back(tmp);
		printf("%d. ",cas++);
		for(p = 0; exp[p]!='='; p++);
		exp[p] = 0;
		init(exp);
		exp[p] = '=';
		num = atoi(&exp[p+1]);
		len = strlen(&exp[p+1]);
		if(len > 7 || num >= 99999 * 51)
		{
			puts("IMPOSSIBLE");
			continue;
		}
		l = len;
		if(l > 5)
			l = 5;
		for(i = 0; i <= num; i++)
			value[i] = 0;
		for(i = 1; i <= p; i++)
		{
			dp[i].clear();
			value[0]++;
			t = i-l+1;
			if(t < 1)
				t = 1;
			char ch = exp[i];
			exp[i] = 0;
			int max = -1;
			for(j = t; j <= i; j++)
			{
				if(exp[j-1]=='0')
					continue;
				int tt = atoi(&exp[j-1]);
				int ttt;
				for(it = 0; it < dp[j-1].size(); it++)
				{
					ttt = tt+dp[j-1][it].value;
					if(ttt > num)
					{
						break;
					}
					if(ttt + maxvalue[i] < num)
					{
						continue;
					}
					if(ttt + minvalue[i] > num)
					{
						break;
					}
					if(ttt <= num)
					{
						if(value[ttt] != value[0])
						{
							if(ttt > max)
								max = ttt;
							value[ttt] = value[0];
							plus[ttt] = dp[j-1][it].num_of_plus+1;
							prev[ttt] = j-1;
						}
						else
						{
							if(dp[j-1][it].num_of_plus+1 < plus[ttt])
							{
								plus[ttt] = dp[j-1][it].num_of_plus+1;
								prev[ttt] = j-1;
							}
						}
					}
				}
			}
			for(it = 1; it <= max; it++)
			{
				if(value[it]==value[0])
				{
					tmp.value = it;
					tmp.num_of_plus = plus[it];
					tmp.prev = prev[it];
					dp[i].push_back(tmp);
				}
			}
			exp[i] = ch;
		}
		if(dp[p][dp[p].size()-1].value==num)
		{
			int pos[257];

			memset(pos,0,sizeof(pos));
			len = p;
			tmp = dp[len][dp[p].size()-1];
			int nn = num;
			while(tmp.prev!=-1)
			{
				pos[tmp.prev] = 1;
				int tt = getnum(&exp[tmp.prev],len-tmp.prev);
				len = tmp.prev;
				nn -= tt;
				int index = find_in_dp(tmp.prev,nn);
				tmp = dp[tmp.prev][index];
			}
			pos[0] = 0;
			for(i = 0; exp[i]; i++)
			{
				if(pos[i])
					putchar('+');
				putchar(exp[i]);
			}
			putchar('\n');
		}
		else
			puts("IMPOSSIBLE");
	}
	return 0;
}