Codeforces ECR #104 : F. Ones

本番Gは解けたのにFが解けず。
https://codeforces.com/contest/1487/problem/F

問題

50桁以内の正整数Nが与えられる。
Nを、1だけで構成される正整数の加減算で表現したい。
正整数はいくつ必要か。

解法

下の桁から決めていく。
その際、carry及びプラスの項、マイナスの項がいくつあるかを状態として持てばよい。

string S;
int from[62][255][255];
int to[62][255][255];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	reverse(ALL(S));
	S+="0";
	memset(from,0x3f,sizeof(from));
	from[30][254][254]=0;
	int p,n;

	FOR(i,S.size()) {
		memset(to,0x3f,sizeof(to));
		for(int ca=1;ca<=59;ca++) for(p=254;p>=0;p--) for(n=254;n>=0;n--) if(from[ca][p][n]<=1<<20) {
			if(p) chmin(from[ca][p-1][n],from[ca][p][n]);
			if(n) chmin(from[ca][p][n-1],from[ca][p][n]);
			int val=ca-30+p-n;
			int nexc=val/10;
			int d=(val%10+10)%10;
			
			if(d&&val<0) nexc--;
			if(d==S[i]-'0') {
				chmin(to[30+nexc][p][n],from[ca][p][n]+p+n);
			}
			
		}
		swap(from,to);
	}
	
	int mi=1<<20;
	FOR(p,255) FOR(n,255) mi=min(mi,from[30][p][n]);
	cout<<mi<<endl;
}

まとめ

解法はシンプルなんだけど、とっさに思いつかないもんだね。