いくつかのダイナミックな計画のテーマ

1. POJ 1080 Human Gene Functions
この問題は3つの状況に分ける必要があります.2つの列がs 1,s 2に分かれていると仮定します.
dp[i][j]がi長を表すs 1とj長のs 2が一致する最大スコアを設定する
次のような状況があります
1)s 1はs 1[i],s 2はs 2[j],dp[i][j]=dp[i-1][j-1]+score(s 1[i],s 2[j])をとる.
2)s 1はs 1[i],s 2は「-」,dp[i][j]=dp[i-1][j]+score(s 1[i],'-')
3)s 1は「-」,s 2はs 2[j],dp[i][j]=dp[i][j-1]+score('-',s 2[j])
ではdp[i][j]は3つのケースの最大値をとるだけでよい
初期化の問題は注意が必要で、明らかにdp[0][0]=0
dp[i][0] = dp[i - 1][0] + score(s1[i], '-')
dp[0][i] = dp[0][j - 1] + score('-', s2[j])
コードは次のとおりです.

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
int dp[105][105];
int table[5][5] =
{{5, -1, -2, -1, -3},
{-1, 5, -3, -2, -4},
{-2, -3, 5, -2, -2},
{-1, -2, -2, 5, -1},
{-3, -4, -2, -1, 0}};
int get(char c)
{
    switch(c)
    {
        case 'A': return 0;
        case 'C': return 1;
        case 'G': return 2;
        case 'T': return 3;
        case '-': return 4;
        default: return 100;
    }
}
int main()
{
    int T;
    char s1[105], s2[105];
    scanf("%d", &T);
    while(T--)
    {
        int len1, len2;
        scanf("%d %s", &len1, s1);
        scanf("%d %s", &len2, s2);
        dp[0][0] = 0;
        for(int i = 1; i <= len1; i++)
        dp[i][0] = dp[i - 1][0] + table[get(s1[i - 1])][get('-')];
        for(int i = 1; i <= len2; i++)
        dp[0][i] = dp[0][i - 1] + table[get('-')][get(s2[i - 1])];
        for(int i = 1; i <= len1; i++)
        {
            for(int j = 1; j <= len2; j++)
            {
                dp[i][j] = max(dp[i - 1][j - 1] + table[get(s1[i - 1])][get(s2[j - 1])], max(dp[i - 1][j] + table[get(s1[i - 1])][get('-')], dp[i][j - 1] + table[get('-')][get(s2[j - 1])]));
            }
        }
        printf("%d
", dp[len1][len2]);
    }
    return 0;
}

2. POJ 1157   LITTLE SHOP OF FLOWERS
この問題の大意はいくつかの花をいくつかの花瓶の中に置いて、それから得た点数を最大にして、マッチングの問題のように見えますが、ダイナミックな計画は明らかにもっと便利です.
私たちはdp[i][j]でi輪の花がj個の瓶に置かれた最大スコアを表す.
i番目の花にj番目の瓶を入れたとき
j>iの場合、i番目の花がj番目の瓶に置かれているとは限らないことは明らかである.
j<=iの場合、i番目の花は必ずj番目の瓶に入れます
状態遷移方程式がある
 if(j > i) dp[i][j] = max(dp[i - 1][j - 1] + score[i][j], dp[i][j - 1]); else dp[i][j] = dp[i - 1][j - 1] + score[i][j];
dp配列は0に初期化すればよい
実装コードは次のとおりです.

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1000000000
using namespace std;
int dp[105][105];
int table[105][105];
int main()
{
    int f, v;
    scanf("%d%d", &f, &v);
    for(int i = 1; i <= f; i++)
    {
        for(int j = 1; j <= v; j++)
        scanf("%d", &table[i][j]);
    }
    for(int i = 1; i <= f; i++)
    {
        for(int j = 1; j <= v; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + table[i][j];
            if(j > i) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
        }
    }
    printf("%d
", dp[f][v]);
    return 0;
}

3. POJ 1160 Post Office
この問題は前の2つより少し複雑だ.
私たちはcost[i][j]でiつの郵便局がjつの村を制御する際の最短距離と
私たちはまず郵便局の状況を見て、1つの郵便局の時、どれだけの村があっても、郵便局は必ずすべての村の中央に置くのが一番だと証明するのは難しくありません.
では状態遷移方程式を得ることができ,newcost[i][j]はiからj村まで郵便局によって制御されたときの最短距離と
cost[i][j] = min(cost[i - 1][k]) + newcost[k + 1][j] 
i-1の郵便局がj村のうちk村を制御し、iの郵便局がj村を制御する最短距離とcost[i-1][k]にi番目の郵便局が制御する残りのk+1からj村までの距離とを加えると、
明らかにnewcost配列は前処理可能であり,kの決定も列挙する必要がある.
実装コードは次のとおりです.

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1000000000
using namespace std;
int cost[305][305];
int newcost[305][305];
int pos[305];
int m, n;
int main()
{
    while(scanf("%d%d", &m, &n) != EOF)
    {
        for(int i = 1; i <= m; i++)
        scanf("%d", &pos[i]);
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                newcost[i][j] = 0;
                int mid = (i + j) >> 1;
                for(int k = i; k <= j; k++)
                newcost[i][j] += abs(pos[mid] - pos[k]);
            }
        }
        for(int i = 1; i <= m; i++)
        cost[1][i] = newcost[1][i];
        for(int i = 2; i <= n; i++)
        {
            for(int j = i; j <= m; j++)
            {
                int mi = INF;
                for(int k = i - 1; k < j; k++)
                {
                    if(mi > cost[i - 1][k] + newcost[k + 1][j])
                    mi = cost[i - 1][k] + newcost[k + 1][j];
                }
                cost[i][j] = mi;
            }
        }
        printf("%d
", cost[n][m]);
    }
    return 0;
}