EDPC-X Tower

X - Tower
高度典型のナップザック問題
例えば、「 を満たすについて番目を番目より下においては行けない」ってルールがあればただのナップザック問題なので解ける
このような順番が定義されていれば解けるタイプの問題は、 自分で適切な順番を定義することで解けることが多い
ここでいう適切な順番と言うのは任意の入力に対して最良ケースのうち少なくとも一つが「ブロックが上からインデックスで単調増加になる」ようなインデックスの付け方
要するに適切な比較演算子を見つける問題
そこでそのようなソートを行う比較演算子について考える
つまり下記のcmpが書ければok（このcmpは全順序の規則*1を満たすとする）

struct block{int w,s;long long v;};
bool cmp(block a,block b){
  //return (aの方がbより必ず上に来るべき);
}

「の方がより必ず上に来るべき」と言うのがどのような時に言えるかなんだけど、
(i)をより上に置く任意のケースにおいて、との場所だけ交換させても問題ない
と言うのが一番分かりやすい言い換え
これを満たしていればをより上に置くメリットが存在しなくなるので、「の方がより必ず上に来るべき」と言える
そしてここから更にもう一段階言い換えると、
(ii)をの真上に置く任意のケースにおいて、との場所だけ交換させても問題ない
となる
この言い換えは一見するとをの真上に置く時のみを否定していて、の上にいくつかのブロックが乗ってその上にが乗ってるパターンを否定していないように見える
しかしそのようなパターンは、との間の任意の隣接している2個の間について(ii)を考えることで推移律から帰納法により否定されることがちょっと考えれば分かる
あとはをの真上に置く、をの真上に置くときそれぞれで満たしていないと行けない条件を確認すれば良い
a,bよりさらに上にあるブロックたちをover,下にあるブロックたちをunderと呼ぶと

X:がの真上の時に満たされる条件

Y:がの真上の時に満たされる条件

探しているのは「Xが満たされているならYを必ず満たす」の条件
Yの1つ目の式はXの2つ目の式が満たされているなら明らかに満たされる
Yの3つ目の式はXの3つ目の式と同値
よって、 X（特に） ならば
となるの条件がわかればいい
これは少しいじればであることが分かる
よって

struct block{int w,s;long long v;};
bool cmp(block a,block b){
 return a.w+a.s<b.w+b.s;
}

とすればよい

#include <bits/stdc++.h>
using namespace std;

struct block{int w,s;long long v;};
bool cmp(block a,block b){
  return a.w+a.s<b.w+b.s;
}
long long ans,dp[20001];

template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}

int main(){
  int n;cin>>n;
  vector<block> a(n);
  for(int i=0;i<n;i++){
    int w,s,v;cin>>w>>s>>v;
    a[i]={w,s,v};
  }
  sort(a.begin(),a.end(),cmp);
  for(int i=0;i<n;i++)
    for(int j=a[i].s;j>=0;j--)chmax(dp[j+a[i].w],dp[j]+a[i].v);
  for(int i=0;i<20001;i++)chmax(ans,dp[i]);
  cout<<ans<<endl;
}

Submission #11383416 - Educational DP Contest

*1:大事なのは推移律の部分