P3283 [SCOI2013]火柴棍数字 DP

题意：

给定一个 (n) 位的数字，求最多移动 (k) 根火柴棒， 能形成的最大值

范围&性质： (1le n le 500,1le k le 3500)

分析：

首先有几个很显然的贪心性质：

1. 位数越多越好
2. 补的前几位都是 1 (最高位有可能是7)

所以问题转化成对于原序列，再拿出尽可能多的火柴棒的前提下，留下的最大值是多少

直接DP，设 (f_{i,j,k}) 表示从小到大第 (i) 位 此时有 (j) 根空闲的火柴棒 这一位是否变成 (0)的情况下最小的移动次数， 转移的时候就枚举这一位变成了什么，所以需要提前预处理出任意两个数之间转化时会增加多少空闲的火柴棒，增加多少移动次数

代码:

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	//8 从左到右 从上到下 依次标号 
	const int maxn = 3505;
	int n,m,sum,len,use;
	short f[maxn>>1][maxn<<1][2];
	int del[11][10],add[11][10];
	//int s[10]={111,96,62,124,105,93,95,100,127,125};
	int s[10]={126,48,107,121,53,93,95,112,127,125};
	char ch[maxn];
	
	void init()
	{
		for(int i=0;i<=9;i++)
		{
			for(int j=0;j<=9;j++)
			{
				for(int k=0;k<=6;k++)
				{
					if(!(s[i]>>k&1)&&(s[j]>>k&1)) del[i][j]++,add[i][j]++;
					if((s[i]>>k&1)&&!(s[j]>>k&1)) add[i][j]--;
				}
			}
		}
		for(int i=0;i<=9;i++)
		{
			for(int k=0;k<=6;k++)
			{
				if(s[i]>>k&1) add[10][i]++,del[10][i]++;
			}
		}
	}
	
	void work()
	{
		init();
		scanf("%s",ch+1);
		scanf("%d",&m);
		n=strlen(ch+1);
		reverse(ch+1,ch+n+1);
		for(int i=1;i<=n;i++) ch[i]-='0';
		for(int i=1;i<=n;i++) sum+=del[10][ch[i]];
		len=sum>>1;
		for(int i=n+1;i<=len;i++) ch[i]=10;
		for(int i=0;i<=len;i++) for(int j=-m;j<=m;j++) f[i][j+maxn][0]=m+1,f[i][j+maxn][1]=m+1; 
		f[0][maxn][0]=0;
		for(int i=0;i<len;i++)
		{
			for(int j=-m;j<=m;j++)
			{
				for(int k=0;k<=1;k++)
				{
					if(f[i][j+maxn][k]<=m)
					{
						for(int x=0;x<=9;x++) 
						f[i+1][j+maxn+add[ch[i+1]][x]][x==0]=min(f[i+1][j+maxn+add[ch[i+1]][x]][x==0],(short)(f[i][j+maxn][k]+del[ch[i+1]][x]));
					}	
				}
			}
		}
		while(f[len][maxn][0]>m) len--;
		for(int i=0;i<=len;i++) for(int j=-m;j<=m;j++) f[i][j+maxn][0]=min(f[i][j+maxn][0],f[i][j+maxn][1]);
		sum=0;
		for(int i=len;i;i--)
		{
			for(int j=9;j>=0;j--)
			{
				sum+=add[ch[i]][j];
				use+=del[ch[i]][j];
				if(f[i-1][maxn-sum][0]<=m-use)
				{
					printf("%d",j);
					break;
				}
				sum-=add[ch[i]][j];
				use-=del[ch[i]][j];
			}
		}
	}

}

int main()
{
	zzc::work();
	return 0;
}