HNU-Flight Boarding Optimization的一些感想

        題目大意：一架飛機，有s列，n個人按順序上飛機，每個人都有一個憤怒值（他座位前面的人數，後面和同列的看不到），現在将飛機分成k節，要求得到的憤怒值最小

        資料範圍：0<n，s<=1000，k<=50。

        題目連結：HNU  官方oj

        對于這題，其實第一眼看到就很有感覺，用博士的話說，就是看到靶子了，這就是一個區間劃分問題，dp轉移方程很快就能寫出來：

                                                   dp[k][i] = min(dp[k][i],dp[k-1][j]+mapt[j+1][i])（dp數組表示前i列分成k段能取到的最優值，mapt是一段區間内所産生的憤怒值）

        時間複雜度：O（s^2 * k）在接受範圍内！！！

        是以，本題的關鍵并不是在這裡。

        該題要想拿到一個好的分數，預處理很關鍵，一開始我的想法是用線段樹維護，因為它求的值和區間息息相關，并且，每一次它都要動态更新數組。于是開始敲起代碼。但一到敲代碼才發現，沒有那麼簡單。根本無從下手。

        在練習結束後各種度娘，找到一篇官方題解，俄文，标程也看不懂。找了好久才找到一篇看的懂的題解，才發現預處理真的好巧妙。

        對于x,y兩個人，如果x<y，且x在y之前上飛機，那麼x必定會對y産生影響。對此，我們将它轉化為二維坐标上的點，坐标就是（x,y），那麼要求出區間【left，right】的憤怒值，就轉化為求二維坐标中矩形（left,left）--(right,right)中點的個數（so easy！！！！）求矩形中的點的個數可以直接用mapt[i][j]+=mapt[i-1][j]+mapt[i][j-1]-mapt[i-1][j-1]轉移（左下角為原點）

#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<stack>
using namespace std;
#define sf scanf
#define pf printf
#define rt return
#define ct continue
#define bk break
#define ms memset
#define REP(i,x,y) for(int i=(x);i<=(y);i++)
#define MAXN 1005
#define INF 0x3fffffff
int n,m,k;
int mapt[MAXN][MAXN];
int dp[55][MAXN];
int people[MAXN];
bool init()
{
    if(sf("%d%d%d",&m,&n,&k)==EOF) rt false;
    REP(i,1,m) sf("%d",&people[i]);
    rt true;
}
void doit()
{
    ms(mapt,0,sizeof(mapt));
    REP(i,1,m)
      REP(j,i+1,m)
        if(people[i]<people[j])
            mapt[people[i]][people[j]]++;
    REP(i,1,n)
      REP(j,1,n)
        mapt[i][j]+=mapt[i-1][j]+mapt[i][j-1]-mapt[i-1][j-1];
    REP(i,0,k)
      REP(j,0,n)
        dp[i][j] = INF;
    dp[0][0]=0;
    REP(i,1,n)
      dp[0][i] = mapt[i][i];
    REP(t,1,k-1)
      REP(i,t,n)
        REP(j,t-1,i-1)
          {
              int tt = mapt[i][i]-mapt[j][i]-mapt[i][j]+mapt[j][j];
              if(dp[t][i]>dp[t-1][j]+tt)dp[t][i]=dp[t-1][j]+tt;
          }
    pf("%d\n",dp[k-1][n]);
}
int main()
{
    while(init())
    {
        doit();
    }
    rt 0;
}
           

這個代碼可以過官方oj，但在湖大oj上一直TLE（或許可以用單調隊列優化，不過我沒試）

再附個标程（我看不懂，如果有大神看懂，請幫忙解釋解釋）

#include <cstdio>
const int INF = 1 << 30;
int d[1234][1234];
int dp[1234], ne[1234], a[1234];
int main() {
  int n, s, k;
  scanf("%d%d%d", &n, &s, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    --a[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (a[i] >= a[j]) continue;
      d[a[i]][a[j]]++;
    }
  }
  for (int i = s - 1; i > 0; i--) {
    for (int j = 0; j < s; j++) {
      d[i - 1][j] += d[i][j];
    }
  }
  for (int i = 0; i < s; i++) {
    for (int j = 1; j < s; j++) {
      d[i][j] += d[i][j - 1];
    }
  }
  for (int i = 0; i <= s; i++) {
    dp[i] = INF;
  }
  dp[0] = 0;
  for (int st = 0; st < k; st++) {
    for (int i = 0; i <= s; i++) ne[i] = INF;
    for (int i = 0; i < s; i++) {
      for (int j = i; j < s; j++) {
        if (ne[j + 1] > dp[i] + d[i][j]) {
          ne[j + 1] = dp[i] + d[i][j];
        }
      }
    }
    for (int i = 0; i <= s; i++) dp[i] = ne[i];
  }
  printf("%d\n", dp[s]);
}