更新日志
概念
类似于状态压缩DP，但我们储存的是轮廓线上的状态。
有些时候，也不需要进行状态压缩，而可以用某一点的状态代表一个区域的状态。
思路
轮廓线就是已经决策的与尚未决策的部分的分界线，我们储存分界线上已经决策过的所有节点的状态。
借图OI-wiki：
图中最粗的那一条就是轮廓线。储存的状态可以为第三行前两个与第二行后两个。
直接上例题。
例题
HDU1400
骨牌覆盖，经典问题。
我们考虑状态，\(0\) 表示尚未被覆盖，\(1\) 表示已经被覆盖。
我们是逐格推进的。每次更新时，都只需要枚举这一格的轮廓线状态。（当前格视作已决策的情况下）
- 当前格子状态为 \(0\)。
那么只能不放。因此，由于要填满整个棋盘，它上面的格子必须已经被覆盖，也就是必须为 \(1\)，可以用异或表示（因为二者在同一位上，且当前位为 \(0\)）
在下方代码中，\(t\) 表示当前所在格子编号，\(s\) 表示状态，\(j\) 表示横坐标。\[f[t][s]=f[t-1][s\oplus 1<<j] \] - 当前格子状态为 \(1\)。
那么可以横着放，也可以竖着放。- 横着放，要求前一位必须为空（至少得有前一位，不能放出界）。同时，当前状态的前一位状态也应该是 \(1\)，因为横着放必然也会盖上其左侧的格子。所以也可以使用异或表示。
同时，这个格子的上面一个格子必须已经被覆盖了，由于这一位状态本来就是 \(1\)，所以可以直接使用，无需改变状态。\[f[t][s]=f[t][s]+f[t-1][s\oplus 1<<j-1] \] - 竖着放，对于前一位就没有什么要求了，但是这一位的上一个格子必须为 \(0\)，同理可得异或即可。\[f[t][s]=f[t][s]+f[t-1][s\oplus 1<<j] \]
- 横着放，要求前一位必须为空（至少得有前一位，不能放出界）。同时，当前状态的前一位状态也应该是 \(1\)，因为横着放必然也会盖上其左侧的格子。所以也可以使用异或表示。
初始化：第一行的前一行视作全部填满，其他状况均无可能。
答案：最后一行不能留空，答案就是 \(f[t][(1<<m)-1]\)。\(m\) 表示总列数。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define dprint(x) cout<<#x<<"="<<x<<"\n"
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7/*998244353*/;
const int N=11;
int n,m;
ll f[2][2<<N];
ll ans;
void solve(){
if(n<m)swap(n,m);
int i,wc;
memset(f,0,sizeof(f));
f[0][(1<<m)-1]=1;
ans=0;
for(i=0,wc=1;i<n;i++){
for(int j=0;j<m;j++,wc^=1){
for(int s=0;s<(1<<m);s++){
if(s>>j&1){
f[wc][s]=f[wc^1][s^(1<<j)];
if(j>0&&(s>>j-1&1))f[wc][s]+=f[wc^1][s^(1<<j-1)];
}else f[wc][s]=f[wc^1][s^(1<<j)];
}
}
}
cout<<f[wc^1][(1<<m)-1]<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
while(cin>>n>>m)solve();
return 0;
}
LG1437
可以用最下侧的点状态表示其一整个倒三角的状态。
分别储存删除这个点的价值和使这个三角形为空的最大价值即可。
考虑从其右上角转移得到当前点，然后加上与它同列且在其上方的所有价值，代表删除这个点。
是这个三角形为空，可以先使它下面一个三角形为空，也可以删除当前节点，更新即可。
实时统计答案。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define dprint(x) cout<<#x<<"="<<x<<"\n"
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7/*998244353*/;
const int N=55;
int n,m;
int a[N][N];
ll s[N][N];
ll res[N][N][N*N];//使三角空
ll dlt[N][N][N*N];//删除这个三角
ll ans;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
cin>>a[i][j];
s[i][j]=s[i-1][j]+a[i][j];
}
}
//right->left down->up
for(int j=n;j>=1;j--){
for(int i=n-j+1;i>=0;i--){
for(int k=i*(i+1)/2;k<=m;k++){
dlt[i][j][k]=res[max(0,i-1)][j+1][k-i]+s[i][j];
res[i][j][k]=max(res[i+1][j][k],dlt[i][j][k]);
ans=max(ans,res[i][j][k]);
}
}
}
cout<<ans;
return 0;
}