POJ 1015 배심원 인선 [동적 기획]

동적 기획이 너무 심오하고 규정하기 어렵다. 이 문제는 에서 언급한 사고방식과 코드를 보고 구체적인 기획 사고방식은 다음과 같다.
 
f[i][j]로 i명의 후보자를 뽑아 j의 모든 방안에서 변호와 제어가 가장 큰 방안의 변호와 제어를 나타낸다.
f[i][j]가 실행 가능한 방안 f[i-1][x]에서 진화할 것을 요구한다.실행 가능한 방안 f(i-1, x)가 방안 f(j, k)로 진화할 수 있는 필수 조건은 다음과 같다.
어떤 후보 k가 존재하고 k는 방안 f(i-1, x)에서 뽑히지 않았으며 x+V(k)=j;(V(k)는 제k개인의 변론차이이다).
f(i-1,x)+S(k)(변론과)의 값이 가장 큰 것을 고르면 방안 f(i-1,x)에 후보 k를 더하면 방안 f(i,j)로 변한다.
이 가운데 하나의 방안을 모두 어떤 사람을 뽑았는지 기록해야 한다.방안 f(i,j)에서 마지막으로 뽑은 후보의 번호를 2차원에 기록해도 무방하다
배열의 요소 path[i][j]에 있습니다.그러면 방안 f(i, j)의 밑에서 두 번째 인선의 번호는 바로 path[i-1][j-V[path[i][j]]이다.
마지막으로 방안을 이해하는 변제차가 k라고 가정하면 path[m][k]에서 출발하여 한 걸음 한 걸음 뽑힌 모든 후보를 구할 수 있다.

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

int compare(void const* a, void const* b)
{
    return *(int*)a - *(int*)b;
}

int main()
{
    int n, m, i, j, k, t1, t2, casenum=1, min;
    int f[21][1000], p[201], d[201], path[21][1000];
    int Qnum[21], Q[21][900]; //  
    int ans[21];

    while (scanf("%d %d", &n, &m) && n)
    {
        memset(f, -1, sizeof(f));   //    ！！     -1;    ？？？
        memset(Qnum, 0, sizeof(Qnum));
        for (i=1; i<=n; i++)
        {
            scanf("%d %d", &p[i], &d[i]);
        }

        Q[0][0] = 400;
        Qnum[0] = 1;
        f[0][400] = 0;
        for (i=0; i<m; i++)
        {
            for (j=0; j<Qnum[i]; j++)
            {
                for (k=1; k<=n; k++)
                {
                    if(f[i][Q[i][j]]+p[k]+d[k] > f[i+1][Q[i][j]+p[k]-d[k]])
                    {
                        t1 = i;        //    k     f[i][Q[i][j]]    
                        t2 = Q[i][j];
                        while (t1>0 && path[t1][t2]!=k)
                        {
                            t2 -= p[path[t1][t2]]-d[path[t1][t2]];
                            t1--;
                        }
                        if (t1==0) //     ，  
                        {
                            if (f[i+1][Q[i][j]+p[k]-d[k]] == -1)
                            {    //     
                                Q[i+1][Qnum[i+1]] = Q[i][j]+p[k]-d[k];
                                Qnum[i+1]++;
                            }
                            f[i+1][Q[i][j]+p[k]-d[k]] = f[i][Q[i][j]]+p[k]+d[k];
                            path[i+1][Q[i][j]+p[k]-d[k]] = k;
                        }
                    }
                }
            }
        }
        min = 900;       //                
        for (i=0; i<Qnum[m]; i++)
        {
            if (abs(Q[m][i]-400) < min) min = abs(Q[m][i]-400);
        }
        if (f[m][400+min] > f[m][400-min]) min = min+400;  //            
        else min = 400-min;
        printf("Jury #%d
", casenum++);
        printf("Best jury has value %d for prosecution and value %d for defence:
",
                                  (min-400+f[m][min])/2, (400-min+f[m][min])/2);

        for (i=0; i<m; i++) //           m  
        {
            ans[i] = path[m-i][min];
            min -= p[ans[i]]-d[ans[i]];
        }
        qsort(ans, m, sizeof(int), compare);

        for (i=0; i<m; i++)
          printf(" %d", ans[i]);
        printf("

");
    }
}