题目链接：http://codeforces.com/contest/339/problem/C
题目大意：
在天平上放砝码
你要在左边放一下然后到右边放一下
一直重复这样放m次
每次你放在其中一边都要让另外一边的重量比你少
你可以用1~10中的某些砝码
问你要怎样放才行,或者告知系统不能放m次

思路：
开始思路是dp[i][k]表示第i次放砝码k。左右的质量差。后来发现这个差有多个，我们不确定哪一个是最优。那么就没有无后效性。我们再加一维
dp[i][k][w]：dp[i][k]表示第i次放砝码k。左右的质量差为w的状态是否存在。

回溯一下输出路径就可以了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int dp[1005][15][15];
vector<int> v, ans;

int main()
{
    int n, m, x;
    for(int i=1; i<=10; i++){
        scanf("%1d", &x);
        if(x==1){
            v.push_back(i);
        }
    }
    scanf("%d", &m);
    n=v.size();

    if(m==1){
        if(n==0){
            printf("NO\n");
            return 0;
        }
        else{
            printf("YES\n");
            printf("%d\n", v[0]);
            return 0;
        }
    }

    for(int i=0; i<n; i++){
        dp[1][i][v[i]]=1;
    }
    for(int i=2; i<=m; i++){
        for(int j=0; j<n; j++){
            for(int k=0; k<n; k++){
                for(int w=1; w<10; w++){
                    if(j==k){
                        continue;
                    }
                    if(dp[i-1][k][w]&&v[j]>w){
                        dp[i][j][v[j]-w]=1;
                    }
                }
            }
        }
    }
    for(int i=0; i<n; i++){
        for(int w=1; w<10; w++){
            if(dp[m][i][w]){
                printf("YES\n");
                int s=w, u=i;
                ans.push_back(v[u]);
                for(int k=m-1; k>=1; k--){
                    for(int p=0; p<n; p++){
                        if(p!=u&&v[u]>s&&dp[k][p][v[u]-s]){
                            ans.push_back(v[p]);
                            s=v[u]-s;
                            u=p;
                            break;
                        }
                    }
                }
                for(int i=ans.size()-1; i>=0; i--){
                    printf("%d ", ans[i]);
                }
                return 0;
            }
        }
    }
    printf("NO\n");

	return 0;
}