D. Match Stick Game

分析

赛中也不会做,赛后别人说是dp,也思考了好一会儿,本来以为代码会比较难码,结果一发就过了

d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k] 代表现在到了第i个字符,用了j根木棍,前面的符号为k (k = 0 ,表示为正,k = 1 代表负)
从后往前记录每一位的权值 v a l u e [ i ] , v a l u e [ i ] = 1 value[i], value[i] = -1 value[i],value[i]=1代表符号
记录每一位是符号还是数字,记录每一位是否可以是0,(不能有前导零)
c a n l i n g [ i ] = t r u e canling[i] = true canling[i]=true代表可以为0
然后如果第i位为符号位,枚举是放正号还是负号
如果第i位是数字,枚举是 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 0,1,2,3,4,5,6,7,8,9 0,1,2,3,4,5,6,7,8,9

代码


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =1e18;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 100,maxm = 700+10;
LL dp[maxn][maxm][2];// dp[i][j][k] 代表 前i个,共消耗了j个木棍,最后一个符号为k的最大值
// k 为0 代表正,1代表负
char ar[maxn];
LL value[maxn];
bool Canling[maxn];
int stick[10] = {6,2,5,5,4,5,6,3,7,6};
			  // 0 1 2 3 4 5 6 7 8 9
int Get(char c){
	if(c == '+') return 2;
	if(c == '-') return 1;
	return stick[c-'0'];
}
int main(void)
{
    int t;cin>>t;
    while(t--){
    	int n;cin>>n;
    	cin>>(ar+1);
    	int t = 1;
    	int m = 0;
    	for(int i = n; i >= 1; --i){
    		if(isdigit(ar[i]))
    			value[i] = t,t = t*10;
    		else 
    			t = 1;
    		if(isdigit(ar[i-1]))
    			Canling[i] = true;
    		if(!isdigit(ar[i-1]) && !isdigit(ar[i+1]))
    			Canling[i] = true;
    		if(!isdigit(ar[i]))
    			value[i] = -1;
    		m += Get(ar[i]);
    	}
    	for(int i = 0;i <= n; ++i)
    		for(int j = 0;j <= m; ++j)
    			for(int k = 0;k < 2; ++k)
    				dp[i][j][k] = -INFF;
    	dp[0][0][0] = 0;
    	for(int i = 1;i <= n; ++i){
    		for(int j = 0;j <= m; ++j){
    			for(int k = 0;k < 2; ++k){
    				dp[i][j][k] = -INFF;
    				if(value[i] == -1){
    					for(int k = 0;k < 1; ++k)
    						if(!k&&j >= 2)
    							dp[i][j][k] = max(dp[i-1][j-2][k],dp[i-1][j-2][k^1]);
    						if(k&&j >= 1)
    							dp[i][j][k] = max(dp[i-1][j-1][k],dp[i-1][j-1][k^1]);
    				}
    				else{
    					for(int l = 0;l < 10; ++l){ // 代表当前位置放l
    						if(l == 0&& !Canling[i]) continue;
    						if(j < stick[l]) continue;
    						int add = k==0?1:-1;
    						add = 1ll*l*value[i]*add;
    						dp[i][j][k] = max(dp[i-1][j-stick[l]][k]+add,dp[i][j][k]);
    					}
    				}
    			}
    		}
    	}
    	cout<<max(dp[n][m][0],dp[n][m][1])<<endl;
    }

   	return 0;
}