POJ 1015 陪审团问题

题意略。

思路：

这个题目开始我本来打算用个二维dp，令dp[ i ][ j ]为考虑前i个人，有j个名额的时候，我所能获取的最小差，后来发现不好转移。因为dp[ i ][ j ]有可能是+2，

也有可能是-2，这两种值对我以后的求解可能都有用。后来想再添加一维，dp[ i ][ j ][ 0 ]表示正值的最小，dp[ i ][ j ][ 1 ]表示负值的最小（绝对值的最小）。

这样dp逻辑又很复杂。最后参考了网上的解法，于是将状态定义为:

dp[ i ][ j ][ k ]表示在前i个人里考虑，有j个名额，使得sigma(p) - sigma(d)为k时，我所能获得的sigma(p + d)的最大值。

状态转移方程：dp[ i ][ j ][ k ] = max(dp[i - 1][ j ][ k ] , dp[i - 1][j - 1][k - p[i] + d[i] ] + p[ i ] + d[ i ])

只可惜我做题时只想到了正负值的问题，没有更进一步将正负值直接确定为差值，然后dp对象为p + d，从而满足题目中的第二个条件。

有时dp对象可以是次要条件，而不是首要条件，换一种方向去思考问题。

内存很紧张

//#include<bits/stdc++.h>

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn1 = ;

const int maxn2 = ;

const int maxn3 = ;

const int mid = maxn3>>;

const int F = 0x3f;

const int INF = 0x3f3f3f3f;

struct node{

    int peo,place,sub;

    node(int peo = ,int place = ,int sub = ){

        this->peo = peo,this->place = place,this->sub = sub;

    }

};

int p[maxn2],d[maxn2],dp[maxn2][maxn1][maxn3],store[maxn2],n,m;

node path[maxn2][maxn1][maxn3];

int main(){

    int cas = ;

    while(scanf("%d%d",&n,&m) ==  && (n + m)){

        for(int i = ;i <= n;++i) scanf("%d%d",&p[i],&d[i]);

        int total =  * m;

        int low = mid - total,up = mid + total;

        for(int i = ;i <= n;++i){

            for(int j = ;j <= m;++j){

                for(int k = low;k <= up;++k){

                    dp[i][j][k] = -;

                    path[i][j][k] = node(-,-,-);

                }

            }

        }

        for(int i = ;i <= n;++i) dp[i][][mid] = ;

        for(int i = ;i <= n;++i){

            int bound = min(i,m);

            for(int j = ;j <= bound;++j){

                for(int k = low;k <= up;++k){

                    int part1 = dp[i - ][j][k];

                    int part2 = (k - p[i] + d[i] < low || k - p[i] + d[i] > up || dp[i - ][j - ][k - p[i] + d[i]] == -) ? - : dp[i - ][j - ][k - p[i] + d[i]] + p[i] + d[i];

                    dp[i][j][k] = max(part1,part2);

                    if(part1 == - && part2 == -) continue;

                    if(part1 > part2) path[i][j][k] = node(i - ,j,k);

                    else path[i][j][k] = node(i - ,j - ,k - p[i] + d[i]);

                }

            }

        }

        int idx;

        for(int i = ;i <= total;++i){

            int lft = mid - i,rht = mid + i;

            int maxx = max(dp[n][m][lft],dp[n][m][rht]);

            if(maxx == -) continue;

            if(maxx == dp[n][m][lft]) idx = lft;

            else idx = rht;

            if(maxx != -) break;

        }

        int tail = ;

        for(int i = n,j = m,k = idx;i != -;){

            node temp = path[i][j][k];

            int nxti = temp.peo;

            int nxtj = temp.place;

            int nxtk = temp.sub;

            if(nxti == -) break;

            if(nxtj < j) store[tail++] = i;

            i = nxti,j = nxtj,k = nxtk;

        }

        int ans1 = ,ans2 = ;

        for(int i = ;i < tail;++i){

            ans1 += p[store[i]];

            ans2 += d[store[i]];

        }

        printf("Jury #%d\n",cas++);

        printf("Best jury has value %d for prosecution and value %d for defence:\n",ans1,ans2);

        for(int i = tail - ;i >= ;--i) printf(" %d",store[i]);

        printf("\n\n");

    }

    return ;

}

/*

4 2

1 2

2 3

4 1

6 2 

10 5

3  8

15  8

11  8

7  8

1  8

17  8

8  8

2  8

13  8

3  8

5 3

13 11

3 17

15 20

6 13

17  9

8 5

 3  5

17 16

 6  0

17 10

 6 14

 3 19

 4 13

 0 17

*/

巴特西

POJ 1015 陪审团问题

最新文章

热门文章