☆【動的計画】木馬級デーモンプロセス

【    】 
  “   ，    ，       ，    。”     。 
                    ，                   
  。      ，                              
        。 
                 ，       ，              
     （      ），      k        ，           。  
           ，  n   m  。            ，        
           ，             。             ，
                k                  。 
 
【    】 
        n，m，k。 
    n     m   ，           。 
 
【    】 
    ，         。 
 
【    】 
4 2 2 
-4 -1 
22 18 
-1 -4 
30 10 
 
【    】 
80 
 
【       】 
   40%     ：m=1； 
   100%   ：1≤n≤100，1≤m≤2，1≤k≤10。 
k           ，       。 
         longint   。

これはダイナミックな計画問題です.まずm=1の場合を考える.状態:前i行でシャットダウンj回で得られる最大価値をf[i][j]で表す.遷移方程式:f[i][j]=max{f[i-1][j],f[k][j-1]+sum[i]-sum[k]}が容易に得られる.ここで、sum[i]は、この列iの接頭辞和を表す.m=2の場合を再考する.ステータス:同上.f値を計算する前にf 0[L][R][j]とf 1[L][R][j]を前処理し、それぞれ1,2列目(L,R)という区間関j回の最大収益を表す.それでは、ステップごとの決定には4種類ある:1)選択しない;2)第一列のサブ矩形を選択する.3)第二列のサブ矩形を選択する.4)第1列および第2列のサブ長方形を選択します.得られる移行方程式:
f[i][j] = max{f[i - 1][j], f[k][j - 1] + sum1[i] - sum1[k] + sum2[i] - sum2[k], f[k][j - u - v] + f0[k][i][u] + f1[k][i][v]}.
ここでsum 1[i]およびsum 2[i]は、それぞれ第1列および第2列iのプレフィックス和を表す.
Accode:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>

const char fi[] = "mua.in";
const char fo[] = "mua.out";
const int maxN = 110;
const int maxK = 20;
const int MAX = 0x3fffff00;
const int MIN = -MAX;

int c[maxN][2];
int sum[maxN][2];
int f[maxN][maxK];
int f0[maxN][maxN][maxK];
int f1[maxN][maxN][maxK];
int n, m, K, ans;

  void init_file()
  {
    freopen(fi, "r", stdin);
    freopen(fo, "w", stdout);
  }

  void readdata()
  {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i < n + 1; ++i)
     for (int j = 0; j < m; ++j)
      {
        int x;
        scanf("%d", &x);
        sum[i][j] = sum[i - 1][j] + x;
      }
  }

  void work1()
  {
    memset(f, 0x80, sizeof(f));
    for (int j = 0; j < K + 1; ++j) f[0][j] = 0;
    for (int i = 1; i < n + 1; ++i)
     for (int j = 0; j <= K && j <= i; ++j)
      {
        f[i][j] = f[i - 1][j];
        if (j) for (int k = 1; k < i + 1; ++k)
          f[i][j] = std::max(f[i][j],
            f[k][j - 1] + sum[i][0] - sum[k][0]);
        ans = std::max(ans, f[i][j]);
      }
  }

  void work2()
  {
    memset(f0, 0x80, sizeof(f0));
    memset(f1, 0x80, sizeof(f1));
    memset(f, 0x80, sizeof(f));
    for (int L = 0; L < n; ++L)
    {
      for (int j = 0; j < K + 1; ++j)
        f0[L][L][j] = f1[L][L][j] = 0;
      for (int R = L + 1; R < n + 1; ++R)
       for (int j = 0; j <= K; ++j)
        {
          f0[L][R][j] = f0[L][R - 1][j];
          f1[L][R][j] = f1[L][R - 1][j];
          if (j) for (int k = L; k < R + 1; ++k)
          {
            f0[L][R][j] = std::max(f0[L][R][j],
              f0[L][k][j - 1] +
              sum[R][0] - sum[k][0]);
            f1[L][R][j] = std::max(f1[L][R][j],
              f1[L][k][j - 1] +
              sum[R][1] - sum[k][1]);
          }
        }
    }
    for (int j = 0; j < K + 1; ++j) f[0][j] = 0;
    for (int i = 1; i < n + 1; ++i)
     for (int j = 0; j <= K && j <= i; ++j)
      {
        f[i][j] = f[i - 1][j];
        if (j)
        {
          for (int k = 1; k < i + 1; ++k)
            f[i][j] = std::max(f[i][j],
              f[k][j - 1] + sum[i][0] - sum[k][0]
              + sum[i][1] - sum[k][1]);
          for (int k = 1; k < i; ++k)
           for (int u = 0; u <= j; ++u)
            for (int v = 0; u + v <= j; ++v)
              f[i][j] = std::max(f[i][j],
                f[k][j - u - v] + f0[k][i][u]
                + f1[k][i][v]);
        }
        ans = std::max(ans, f[i][j]);
      }
  }

  void print() {printf("%d", ans); }

int main()
{
  init_file();
  readdata();
  if (m == 1) work1(); else work2();
  print();
  exit(0);
}

2回目:

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#define max(a, b) ((a) > (b) ? (a) : (b))

const char fi[] = "mua.in", fo[] = "mua.out";
const int maxN = 110, maxK = 20;
const int MAX = 0x3f3f3f3f, MIN = ~MAX;

int f[maxK][maxN][maxN], f1[maxK][maxN];
int sum[maxN][2];
int n, m, K;

void init_file()
{
    freopen(fi, "r", stdin);
    freopen(fo, "w", stdout);
    return;
}

inline int getint()
{
    int res = 0; char tmp; bool sgn = 1;
    do tmp = getchar();
    while (!isdigit(tmp) && tmp != '-');
    if (tmp == '-') {sgn = 0; tmp =getchar();}
    do res = (res << 3) + (res << 1) + tmp - '0';
    while (isdigit(tmp = getchar()));
    return sgn ? res : -res;
}

void readdata()
{
    n = getint(); m = getint(); K = getint();
    for (int i = 1; i < n + 1; ++i)
    for (int j = 0; j < m; ++j)
        (sum[i][j] = getint()) += sum[i - 1][j];
    return;
}

int work1()
{
    for (int k = 1; k < K + 1; ++k)
    for (int i = 1; i < n + 1; ++i)
    {
        f1[k][i] = f1[k][i - 1];
        for (int j = 0; j < i; ++j)
            f1[k][i] = max(f1[k][i], f1[k - 1][j]
                           + sum[i][0] - sum[j][0]);
    }
    return f1[K][n];
}

int work2()
{
    for (int k = 1; k < K + 1; ++k)
    for (int i = 0; i < n + 1; ++i)
    for (int j = 0; j < n + 1; ++j)
    if (i || j)
    {
        if (i == j)
        {
            f[k][i][j] = max(f[k][i][j - 1], f[k][i - 1][j]);
            for (int t = 0; t < i; ++t)
                f[k][i][j] = max(f[k][i][j], f[k - 1][t][t]
                                 + sum[i][0] - sum[t][0]
                                 + sum[i][1] - sum[t][1]);
        }
        else if (i > j)
        {
            f[k][i][j] = f[k][i - 1][j];
            for (int t = 0; t < i; ++t)
                f[k][i][j] = max(f[k][i][j], f[k - 1][t][j]
                                 + sum[i][0] - sum[t][0]);
        }
        else if (i < j)
        {
            f[k][i][j] = f[k][i][j - 1];
            for (int t = 0; t < j; ++t)
                f[k][i][j] = max(f[k][i][j], f[k - 1][i][t]
                                 + sum[j][1] - sum[t][1]);
        }
    }
    return f[K][n][n];
}

int main()
{
    init_file();
    readdata();
    printf("%d
", (m == 1) ? work1() : work2());
    return 0;
}