学步园

 Problem C. Card Game

两次三维DP，没想到还能这样@@

对段【i，j】判断能否被完全消除（j>=i+2)，递推公式是

• ( i，m,j) 可以消除，【i+1,m-1】，【m+1,j-1】可以消除(即i,j作为边界两点和中间某个m点一起消除） i<m<j
•  【i,m】可以消除，【m+1,j】可以消除    i+2<=m<j,m+=3

然后对端【i，j】计算最小剩余牌的数目。【i，j】的count初始化为 j-i+1(初始值）

•  0  if 【i，j】能消除
•  min{ 【i，m】+【m+1，j】}      i<=m<j

#include  <iostream>
#include <vector>
using namespace std;
inline bool isValid(int a,int b,int c,int k){
  return b-a==k&&c-b==k;
}
//[ x y .....],k
int dp(int a[],int n,int c){
  if(n==0) return 0;
  vector<vector<bool> > vec(n+1,vector<bool>(n+1,false));

  for(int i=1;i<=n;i++) vec[i][i-1]=true;//@important:init edge

  for(int i=3;i<=n;i+=3){//@warning:i+=3, a detail
    for(int j=1;j+i-1<=n;j++){
      int k=j+i-1;
      // [j,k]=> j,[j+1,m],m+1,[m+2,k-1],k
      for(int m=j;m+2<=k;m+=3){//@error: here m start from j, not j+1
        vec[j][k]=(vec[j+1][m]&&vec[m+2][k-1]&&isValid(a[j],a[m+1],a[k],c));
        if(vec[j][k]) break;
      }
      if(!vec[j][k]){
        for(int m=j+3;m<k;m+=3){
          if(vec[j][m-1]&&vec[m][k]) {
            vec[j][k]=true;
            break;
          }
        }
      }
    }
  }

  #define maxn 0xfffffff
  vector<vector<int> > cnt(n+1,vector<int>(n+1,maxn));
  for(int i=1;i<=n;i++){
    for(int j=1;j+i-1<=n;j++){
      int k=j+i-1;
      if(vec[j][k]) {cnt[j][k]=0;continue;}
      cnt[j][k]=i;//@important
      for(int m=j;m<k;m++)
        cnt[j][k]=min(cnt[j][k],cnt[j][m]+cnt[m+1][k]);
    }
  }
  return cnt[1][n];
}
int main(){
  int a[10000];
  int n;cin>>n;
  for(int i=0;i<n;i++){
    int m,k;cin>>m>>k;
    for(int j=1;j<=m;j++)//@error: a[] start from 1
      cin>>a[j];
    cout<<"Case #"<<i+1<<": "<<dp(a,m,k)<<endl;
  }
  return 0;
}

另一种写法：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

const int maxn = 105;

int a[maxn], f[maxn][maxn];
bool d[maxn][maxn];

int diff(int a, int b, int c, int k) {
    return c - b == k && b - a == k;
}

int solve() {
    int n, K;
    cin >> n >> K;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    memset(d, 0, sizeof(d));
    for (int i = 1; i <= n; ++i) {
        d[i][i - 1] = true;
    }
    for (int l = 3; l <= n; ++l) {
        for (int i = 1; i + l - 1 <= n; ++i) {
            int j = i + l - 1;
            for (int k = i + 1; k < j; k += 3) {
                d[i][j] |= (d[i + 1][k - 1] && d[k + 1][j - 1] && diff(a[i], a[k], a[j], K));
            }
            for (int k = i + 2; k < j; k += 3) {
                d[i][j] |= (d[i][k] && d[k + 1][j]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            if (d[i][j]) {
                f[i][j] = j - i + 1;
            } else {
                f[i][j] = 0;
            }
        }
    }
    for (int l = 3; l <= n; ++l) {
        for (int i = 1; i + l - 1 <= n; ++i) {
            int j = i + l - 1;
            for (int k = i; k < j; ++k) {
                f[i][j] = std::max(f[i][j], f[i][k] + f[k + 1][j]);
            }
        }
    }
    return n - f[1][n];
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        cout << "Case #" << t << ": " << solve() << endl;
    }
}