POJ 1015 Jury Compromise DP+記錄路徑

POJ 1015 Jury Compromise DP+記錄路徑

找每個點能轉移出去的狀態時要回溯到根去掉所有能轉移的點來去重。。

可能這種做法在距離根距離較小的時候能用。。（隱隱感覺有bug，還是人雲亦雲地做掉先了。。）

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 

template 
inline bool rd(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
template 
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
const int N = 205;
const int M = 25;
using namespace std;
int n, m;
int a[N], b[N];
int dp[M][805], pre[M][805], id[M][805];
bool vis[N];
vectorpath;
void output_path(){
    sort(path.begin(), path.end());
    for(int i = 0; i < (int)path.size(); i++)printf(" %d", path[i]);puts("");
}
void find(int x, int y){
    path.clear();
    while(-1 != pre[x][y]){
        path.push_back(id[x][y]);
        vis[id[x][y]] = 1;
        int tx = pre[x][y]/1000;
        int ty = pre[x][y]%1000;
        x = tx; y = ty;
    }
}
const int mov = 400;
void work(){
    memset(dp, -1, sizeof dp);
    dp[0][mov] = 0; pre[0][mov] = -1;
    for(int i = 0; i < m; i++)
        for(int j = 0; j <= 800; j++)
        {
            if(-1 == dp[i][j])continue;
            memset(vis, 0, sizeof vis);
            find(i, j);
        //    output_path();
            for(int k = 1; k <= n; k++)
                if(0 == vis[k])
                {
                    int tmp = a[k]-b[k];
                    if(dp[i+1][j+tmp] < dp[i][j] + a[k]+b[k])
                    {
                        dp[i+1][j+tmp] = dp[i][j] + a[k]+b[k];
                        pre[i+1][j+tmp] = i*1000+j;
                        id[i+1][j+tmp] = k;
                    }
                }
        }
}
int main(){
    int Cas = 1;
    while(~scanf("%d %d", &n, &m), n+m){
        for(int i = 1; i <= n; i++)rd(a[i]), rd(b[i]);
        printf("Jury #%d\n", Cas++);
        work();
        int ans = -1;
        for(int i = 400; i <= 800; i++)
            if(-1 != dp[m][i] || -1 != dp[m][800-i])
            {
                if(dp[m][i] > dp[m][800-i])
                    ans = i;
                else ans = 800-i;
                break;
            }
        printf("Best jury has value %d for prosecution and value %d for defence:\n", (dp[m][ans]+ans-400)/2, (dp[m][ans]-ans+400)/2);
        find(m, ans);
        output_path();
        puts("");
    }
    return 0;
}