#C231106B. 塔(tower)

前言（Front talk）

做这道题的时候不知道该往哪个方向思考，导致最终没有做出来（也许就算想出来了实现也不会）。

网址（Website）

题目详情 - 塔(tower) - Super

题解 - 塔(tower) - Super

题目（Problem）

小在打隔膜。现在她已经来到了所处建筑物的底部。

所处的建筑物可以视为一座塔。这座塔呈一个三角形，高层，从高到低第层由个排成一列的房间构成。所有房间大小相同且每一层的中心都在一条直线上。用表示从高到低第层的第个房间。

在塔中个房间安插了守卫。小需要消灭这些守卫才能面对。

小有两种法术：

在某一个房间释放第一种法术，击杀该房间的所有守卫，法术的代价为。
在某一个房间释放第二种法术，击杀该房间和下方房间的所有守卫，满足这些房间组成的图案与塔相似且最底下的房间位于最底层。形式化地，如果在释放该法术，从高到低第层到第层均会受到影响，第层受到影响的房间编号为到，法术代价为该法术影响的房间数量（不论房间里是否存在守卫）。

求小 G 消灭所有守卫的最小代价。

范围： $；；；$ 。

题解（Solution）

~~啊啊啊，昨天没有睡好，脑子都是宕机状态，现在只能说是 “ 如懂 ”~~

那就简单说一下这道题的好的思路：

对式子的观察：设当前位置下面（包括自己）有行，其中能覆盖个目标，则很容易推出当时，放大招才会更优，因此，该题有一个非常优秀的优化——（我是一个破折号）直接将上面层除去，然后只看下面的层，可以把优化到。
似有似无的滚动数组优化：很明显，如果要对剩下的几行进行动态规划，虽然时间复杂度与空间复杂度在时均可以过，但是我并不是想讲这一点，我讲的是题解对滚动数组的使用方法：将数组开为 f[N][2] ，引入一个变量p，即可非常简单的获得当前数组f[p][j]与上一个数组f[p^1][k] ，这种方法非常值得学习。
用动态数组代替静态数组：若用静态的数组存下该矩阵，在计算当前位置下面的目标个数会很麻烦，而动态数组解决了这个问题（loc[i].size()） ，有助于在过程中更好的计算答案。
类似尺取法的取数方法：当然这是对于动态数组来说的，详细见代码中的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）

噫！我中了！

知道哪里没有懂了：

题解中表示斜列，表示该斜列的第行，所以每一个转移实际上都是在点上推理的
题解代码（注释版）中第行的表示枚举到第斜列，第行时，前面一列的最优的操作的花费（其中该操作那一列没有被操作覆盖到的点已用操作解决），分析易得，所有的操作一定不可能有包含关系，否则不优，因此上一列的最优操作的位置最多只能与当前列同行，即；
若当前行必须有操作，该列中这一行上方的守卫只能用操作（否则就会有覆盖的区间）。