The Preliminary Contest for ICPC China Nanchang National Invitational and International Silk-Road Programming Contest D

佚名 7年前 (2019-04-20) 随笔 2003人围观抢沙发百度已收录

移动火柴，使表达式的值最大化。

题目存在限制条件，不能删除符号，每一个数字的位数不能发生变化，不能出现前导零，单个数字的值不会超过1e9。在这样的条件限制下，可以通过dp求解。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

定义dp[i][j]，其中i为第i个数字，j为此刻已经使用的火柴总数，dp[i][j]即此时能取得的最大值。

题目没有太多难点，整体就是类似背包的写法，但是存在很多细节，初始化需要特别注意，还有就是要排除前导零的干扰。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<iomanip>
#include<cctype> 
#include<ctime>
using namespace std;
typedef long long ll;
#define edl putchar('\n')
#define sscc ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define FORLL(i,a,b) for(ll i=a;i<=b;i++)
#define ROFLL(i,a,b) for(ll i=a;i>=b;i--)
#define mst(a) memset(a,0,sizeof(a))
#define mstn(a,n) memset(a,n,sizeof(a))
#define zero(x)(((x)>0?(x):-(x))<eps)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int month[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{1,-1},{-1,1}};
const int MAXN=1e4+5;
const int INF=1<<30;
const ll mod=1e9+7;//998244353;
const double eps=1e-8;
const ll inff=0x3f3f3f3f3f3f3f3f;

int cal(char c)
{
	if(c=='+'||c=='1') return 2;
	if(c=='-') return 1;
	if(c=='7') return 3;
	if(c=='4') return 4;
	if(c=='2'||c=='3'||c=='5') return 5;
	if(c=='6'||c=='9'||c=='0') return 6;
	return 7;
}

int a[105],v[7],m[7],f[10][70],p[10];
bool vis[10][70][2];//记忆化搜索是否访问过 
ll dd[10][70][2];//存值 
ll num(int now,int k,bool type)//now表示当前是第几个数字，a[now]为这个数字有几位 
{//k表示分配的火柴数，type=1表示符号设置为正，取最大值，type=0表示符号为负，取最小值 
	if(vis[a[now]][k][type]!=0)//记忆化搜索，否则会超时 
	return dd[a[now]][k][type];
	if(type)
	{
		mstn(f,250);//极小化 
		f[0][0]=0;
		FOR(i,1,a[now])//当前数字的第几位 
		{
			FOR(j,2,7)//第i个数字分配j根火柴 
			FOR(t,0,k-j)
			f[i][t+j]=max(f[i-1][t]+v[j]*p[a[now]-i],f[i][t+j]);
		}
	}
	else
	{
		mstn(f,125);//极大化 
		f[0][0]=0;
		FOR(i,1,a[now])//当前数字的第几位 
		{
			FOR(j,2,7)//第i个数字分配j根火柴 
			FOR(t,0,k-j)
			{
				if(i==1&&j==6)//排除前导零的干扰 
				f[i][t+j]=min(f[i-1][t]+6*p[a[now]-i],f[i][t+j]);
				else
				f[i][t+j]=min(f[i-1][t]+m[j]*p[a[now]-i],f[i][t+j]);
			}
		}
	}
	vis[a[now]][k][type]=1;//表示访问过 
	if(type)
	{
		dd[a[now]][k][type]=f[a[now]][k];
		return f[a[now]][k];
	}
	else
	{
		dd[a[now]][k][type]=-f[a[now]][k];
		return -f[a[now]][k];
	}
	
}
ll dp[105][705];
int main()
{
	mst(vis);
	v[2]=m[2]=1;//分别为使用2至7根火柴时取得的最大/小值 
	v[3]=m[3]=7;
	v[4]=m[4]=4;
	v[5]=5,m[5]=2;
	v[6]=9,m[6]=0;
	v[7]=m[7]=8;
	FOR(i,0,9) p[i]=pow(10,i);
	int T,n,sum,cnt;
	cin>>T;
	string s;
	while(T--)
	{
		mst(a);
		sum=0;//一共有多少根火柴 
		cnt=1;
		cin>>n>>s;
		FOR(i,0,n-1)
		{
			sum+=cal(s[i]);
			if(s[i]=='+'||s[i]=='-')
			cnt++;
			else
			a[cnt]++;
		}
		mstn(dp,250);//将dp值初始化为极小值，这是为了屏蔽不合法情况 
		FOR(i,2*a[1],min(sum,7*a[1]))
		dp[1][i]=num(1,i,1);//第一个数字默认为加号 
		FOR(i,2,cnt)
		{
			FOR(k,0,sum)
			{
				FOR(j,2*a[i]+1,7*a[i]+2)//最小能分配的和最大能分配的 
				{
					if(k+j<=sum)
					{
						if(j!=2*a[i]+1)
						dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]+num(i,j-2,1));
						if(j!=7*a[i]+2)
						dp[i][k+j]=max(dp[i][k+j],dp[i-1][k]+num(i,j-1,0));
					}
					else
					break;
				}
			}
		}
		cout<<dp[cnt][sum]<<endl;
	}
}