3161223_ac_3063ms_42420k.cc

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

#include <stdio.h>
#include <time.h>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

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

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

/*bool cmp(node a,node b)
{
	if(a.value!=b.value)
		return a.value < b.value;
	else
		return a.num_of_plus < b.num_of_plus;
}
*/
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');
	//	printf("%d %d\n",maxvalue[i],minvalue[i]);
	//	system("pause");
	}
}

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

	min = 0;
	max = dp[i].size()-1;
//	for(j = 0; j <= max; j++)
//	{
//		printf("%d ",dp[i][j].value);
//	}
//	printf("\n");
	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;
	}
	assert(NULL);
	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)
	{
	//	double t1 = clock();
		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)
					{
					/*	tmp.value = dp[j-1][it].value+tt;
						tmp.num_of_plus = dp[j-1][it].num_of_plus+1;
						tmp.prev = j-1;
						dp[i].push_back(tmp);*/
						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;
							}
						}
					}
					else
						break;
				}
			}
			for(it = 1; it <= max; it++)
			{
				if(value[it]==value[0])
				{
					if(it+maxvalue[i]<num)
						continue;
					if(it+minvalue[i]>num)
						break;
					tmp.value = it;
					tmp.num_of_plus = plus[it];
					tmp.prev = prev[it];
					dp[i].push_back(tmp);
				}
			}
			//printf("\n%d: %d ",i,dp[i].size());
			//sort(dp[i].begin(),dp[i].end(),cmp);
			/*int et;
			bak.clear();
			for(it = 0; it < dp[i].size(); it++)
			{
				bak.push_back(dp[i][it]);
				et = it;
				while(et<dp[i].size()&&dp[i][et].value==dp[i][it].value)
					et++;
				it = et-1;
			}
			dp[i] = bak;*/
			exp[i] = ch;
		//	printf("%d\n",bak.size());
		//	printf("\n");
		//	for(it = 0; it < dp[i].size(); it++)
		//	{
		//		printf("%d ",dp[i][it].value);
		//	}
		//	printf("\n");
		}
		if(dp[p][dp[p].size()-1].value==num)
		{
			int pos[300];

			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");
	//	double t2 = clock();
	//	printf("%.0lfMS\n",t2-t1);
	}
	return 0;
}
//999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999=4799952