POJ 1837 Balance(ダイナミックプランニング)

これは典型的な動的計画問題であり,最初は状態をどのように記録するかは考えにくいが,平衡の種類数が要求されることが分かったので,dp配列が平衡を保存しているときの種類数を考えることができる.しかし、状態を保存し、最終的な種類数を示す記録状態を比較的良く示す方法を考えるため、dp[i][j]を用いて、前のi個の物品を使用した後、天秤の左右がjに異なる場合の種類数を表すことを試みた.
そこで我々は状態遷移の過程を容易に得ることができ、dp[i]はdp[i-1]の値から、i番目の物品をフックのある位置に置いて、dp[i][j]に移行することができ、dp[i][j]はこれらの合法的な条件を満たすすべてのdp[i-1]の総和である.
さらに注意しなければならないのは、左が右より重いことを発見したとき、jは負の数であるため、jの範囲が7500であることを考慮しているので、これらの下付きjに7500を同時に加えることを容易に考えていることです.そして状態遷移方程式に従って遷移すればよい.
初期状態は本来dp[0][0]=1であるべきであるが、オフセット量を1つ増やした後、それに応じてオフセット量をjの上に加算しなければならない!!!
次はACコードです.

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int det=7500;
const int Max=16000;
int dp[22][Max];
int main()
{
    int x[22],m[22],temp,t;
    int c,g,i,j,k;
    while(scanf("%d %d",&c,&g)!=EOF)
    {
        for(i=1;i<=c;i++)
            scanf("%d",&x[i]);
        for(i=1;i<=g;i++)
            scanf("%d",&m[i]);
        memset(dp,0,sizeof(dp));
        dp[0][det+0]=1;
        for(i=1;i<=g;i++)
        {
            for(j=0;j<=2*det;j++)
            {
                temp=0;
                for(k=1;k<=c;k++)
                {
                    int t=m[i]*x[k]+det;
                    if(j-t+det>=0)
                    {
                        temp+=dp[i-1][j-t+det];
                    }
                }
                dp[i][j]=temp;
            }
        }
        printf("%d
",dp[g][det]);
    }
    return 0;
}