#C231106B. 塔(tower)
标签（Label）
- 动态规划
网址（Website）
题目（Problem）
小 $G$ 在打隔膜。现在她已经来到了 $Boss$所处建筑物的底部。
$Boss$ 所处的建筑物可以视为一座塔。这座塔呈一个三角形，高 $n$ 层，从高到低第 $i$ 层由 $i$ 个排成一列的房间构成。所有房间大小相同且每一层的中心都在一条直线上。用 $(x, y)$ 表示从高到低第 $x$ 层的第 $y$ 个房间。
$Boss$ 在塔中 $k$ 个房间安插了守卫。小 $G$ 需要消灭这些守卫才能面对 $Boss$ 。
小 $G$ 有两种法术：
- 在某一个房间释放第一种法术，击杀该房间的所有守卫，法术的代价为 $3$ 。
- 在某一个房间释放第二种法术，击杀该房间和下方房间的所有守卫，满足这些房间组成的图案与塔相似且最底下的房间位于最底层。形式化地，如果在 $(i, j)$ 释放该法术，从高到低第 $i$ 层到第 $n$ 层均会受到影响，第 $k$ 层受到影响的房间编号为 $(k, j)$ 到 $(k, k-i+j)$ ，法术代价为该法术影响的房间数量 $K+2$（不论房间里是否存在守卫）。
求小 G 消灭所有守卫的最小代价。
范围： $n,k\le10^5；yi≤xi；∀i\not=j:(xi,yi)\not=(xj,yj)；0≤k≤\frac{n(n+1)}2 $。
题解（Solution）
啊啊啊，昨天没有睡好，脑子都是宕机状态，现在只能说是 “ 如懂 ”
那就简单说一下这道题的好的思路：
- 对式子的观察：设当前位置 $(i,j)$ 下面（包括自己）有 $w=n-k+1$ 行，其中能覆盖 $k$ 个目标，则很容易推出当 $3k>\frac{(w+1)\times w}2+2$ 时，放大招才会更优，因此，该题有一个非常优秀的优化——（我是一个破折号）直接将上面 $n-\sqrt{k}$ 层除去，然后只看下面的 $\sqrt{k}$ 层，可以把 $O(n)$ 优化到 $O(\sqrt{n})$ 。
- 似有似无的滚动数组优化：很明显，如果要对剩下的几行进行动态规划，虽然时间复杂度与空间复杂度在 $n=10^5$ 时均可以过，但是我并不是想讲这一点，我讲的是题解对滚动数组的使用方法：将数组开为
f[N][2]，引入一个变量p，即可非常简单的获得当前数组f[p][j]与上一个数组f[p^1][k]，这种方法非常值得学习。 - 用动态数组代替静态数组： 若用静态的数组存下该矩阵，在计算当前位置下面的目标个数会很麻烦，而动态数组解决了这个问题 （
loc[i].size()） ，有助于在 $dp$ 过程中更好的计算答案。 - 类似尺取法的取数方法：当然这是对于动态数组来说的，详细见代码中的
while语句。
代码（Code）
我的代码（原版）
#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;
int n,m,k,s[N];
int f[2][N];
vector<int> loc[N];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
cin>>n>>m;For(i,1,m){
int x=input(),y=input();
loc[y].push_back(n-x+1);
}
k=s[0]=0;
while(s[k]<=3*m) k++,s[k]=k*(k+1)/2+(k>0)*2;//求得会放大招的有效行
For(i,1,k) f[0][i]=inf;//初始化数组
For(i,1,n){
sort(loc[i].begin(),loc[i].end());
int p=i&1;//滚动
int mn=f[p][k]=inf;//初始化
for(int j=1,g=0;j<=k;j++){
while(g<loc[i].size() && loc[i][g]<j) g++;
f[p][j-1]=f[p^1][j] + (loc[i].size()-g)*3;
}
for(int j=0,g=0;j<k;j++){
while(g<loc[i].size() && loc[i][g]<=j) g++;
mn=min(f[p^1][j],mn);
f[p][j]=min(f[p][j],mn + s[j] + (int)(loc[i].size()-g)*3);
}
}cout<<(min(f[n&1][0],f[n&1][1]));
return 0;
}题解代码（原版）
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define oo 0x3f3f3f3f
vector<int>v[N];
int n,m,x,y,K,S[N],f[2][N];
int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
v[y].push_back(n-x+1);
}
K=S[0]=0;
while (S[K]<=m*3)K++,S[K]=K*(K+1)/2+(K>0)*2;
for(int i=1;i<=K;i++)f[0][i]=oo;
for(int i=1;i<=n;i++){
sort(v[i].begin(),v[i].end());
int p=(i&1),mn=f[p][K]=oo;
for(int j=1,k=0;j<=K;j++){
while ((k<v[i].size())&&(v[i][k]<j))k++;
f[p][j-1]=f[p^1][j]+(v[i].size()-k)*3;
}
for(int j=0,k=0;j<K;j++){
while ((k<v[i].size())&&(v[i][k]<=j))k++;
mn=min(mn,f[p^1][j]);
f[p][j]=min(f[p][j],mn+S[j]+(int)(v[i].size()-k)*3);
}
}
printf("%d\n",min(f[n&1][0],f[n&1][1]));
return 0;
} 题解代码（注释版）
感谢 superl61 的友情提供！（博客网址： superl61 ）
#include<bits/stdc++.h>
using namespace std;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define ll long long
const int N=1e5+10,inf=1e9+7;
int n,m,k=0;
ll f[2][N],s[N];
vector<int> v[N];
int main(){
freopen("tower.in","r",stdin);
freopen("tower.out","w",stdout);
scanf("%d%d",&n,&m); int x,y;
F(i,1,m){
scanf("%d%d",&x,&y);
v[y].push_back(n-x+1);//第y条斜线(从左往右)的第n-x+1行(从低到高)存在守卫
}
k=0,s[k]=0; //s[i]:在一个h=i的三角形中释放法术2的花费
while(s[k]<=3*m) ++k,s[k]=1ll*(k+1)*k/2+2;
F(i,1,k) f[0][i]=inf;//初始化:因为第1条斜线不存在所谓继承上一次的答案,不初始化会出错
F(i,1,n){//枚举斜线
sort(v[i].begin(),v[i].end());
int p=(i&1),cnt=0; ll mn=inf;
f[p][k]=inf;//k存的是s>sqrt(m) 的第一个位置,从这里释放法术肯定是不优的
//全部用操作1的最优解
F(j,0,k-1){//枚举守卫的位置
while(cnt<v[i].size() && v[i][cnt]<=j) ++cnt;
f[p][j]=f[p^1][j+1]+(v[i].size()-cnt)*3;
//枚举第i条斜线每个守卫的位置,找最下面j行有多少个守卫
//v[i][k]:第i条斜线的第k个守卫在哪一行 只处理最底部的sqrt(m)行
}//继承上一次的答案
//寻找可能的操作2是否更优
cnt=0;
F(j,0,k-1){
while(cnt<v[i].size() && v[i][cnt]<=j) ++cnt;
mn=min(f[p^1][j],mn);//在前i-1行最优秀的一种施法方案的基础上实施当前法术
f[p][j]=min(f[p][j],mn+s[j]+(int)(v[i].size()-cnt)*3);
}//单独施法
}
printf("%lld",min(f[n&1][1],f[n&1][0]));//施法或不施法
return 0;
}后续（Ending）
为什么这道题还是没有完全理解，啊啊啊啊啊啊啊啊。。。w(ﾟДﾟ)w
还有后续（And Ending）
噫！我中了！
知道哪里没有懂了：
- 题解中 $i$ 表示斜列，$j$ 表示该斜列的第 $j$ 行，所以每一个转移实际上都是在点 $(j,i)$ 上推理的
- 题解代码（注释版）中第 $36$ 行的 $mn$ 表示枚举到第 $i$ 斜列，第 $j$ 行时，前面一列的最优的操作 $2$ 的花费（其中该操作 $2$ 那一列没有被操作 $2$ 覆盖到的点已用操作 $1$ 解决），分析易得，所有的操作 $2$ 一定不可能有包含关系，否则不优，因此上一列的最优操作 $2$ 的位置最多只能与当前列同行，即 $j_{i-1}\leq j_i$ ；
- 若当前行必须有操作 $2$ ，该列中这一行上方的守卫只能用操作 $1$ （否则就会有覆盖的区间）。
疯狂中。。。щ(ʘ╻ʘ)щ
