Codeforces 339C Xenia and Weights

新環境のテストも兼ねて出てました。がDの誤読で酷いことになった。

問題

1〜10までの重さの錘のうち、使うことができる種類のものが与えられる。
個数に制限はなく、無限に使える。

これをm回天秤に以下のルールで乗せる。
交互に違う皿に置く。
2回連続で同じ重さの錘を置いてはいけない。
錘を新たに置いたほうの皿は、前においた皿よりも真に重くならなければならない。

ルールを満たす手順をどれか一通り出力せよ。
存在しなければNOを出力せよ。

方針

DP+経路復元すればいい。
dp[個数][差][直前に置いた錘の重さ]
を更新していく。

ソースコード

string s;
int m, prev[1010][11][11]; //sum, diff, prev

int main(){
	cin >> s >> m;
	memset(prev, -1, sizeof(prev));
	prev[0][0][0]= 0;
	
	rep(i, m) rep(j, 11) rep(k, 11) if(prev[i][j][k] >= 0){
		rep(x, 10) if(s[x] == '1' && x+1 != k && j <= x){
			prev[i+1][x+1-j][x+1] = k;
		}
	}
	int diff = -1, p = -1;
	rep(i, 11) rep(j, 11) if(prev[m][i][j] >= 0){
		diff = i;
		p = j;
	}
	if(diff < 0){
		cout << "NO" << endl;
		return 0;
	}
	
	vi v;
	while(m > 0){
		int np = prev[m][diff][p];
		int ndiff = abs(diff-p);
		
		v.pb(p);
		m--;
		diff = ndiff; p = np;
	}
	reverse(all(v));
	
	cout << "YES" << endl;
	rep(i, v.size()) cout << v[i] << (i==v.size()-1?"\n":" ");
	
	return 0;
}