CSP2021-S 题解

2024-02-23 20:12:34

在前面的话

其实这次比赛总体来说比去年简单一些，可惜我考场的时候没有 debug ，考试的时候整个人的状态也不好，所以考试完全发挥失常

T1

题目链接

廊桥分配

问题解决

想要处理这道题需要引用一个结论：

如果一个飞机在 \(i\) 个廊桥时占用廊桥，那么在 \(i+1\) 个廊桥时也必然占用廊桥

我们可以这样证明理解这个结论：

因为先到的飞机是先占用廊桥的，若这个飞机在 \(i\) 的时候可以占用廊桥，也就是说这个飞机到达的时间和前一个飞离的时间是最接近的，所以多了一个廊桥时，这些飞机的相对关系不会发生变化，所以这个飞机必然能占用廊桥。

也就是说，若离这个飞机最近的飞机在 \(i+1\) 时刻占用廊桥，那么这个飞机在 \(i+1\) 时刻也可以占用廊桥

显然，第一个到达的飞机是可以占用廊桥的 (如果廊桥数大于一)

有点像数学归纳法的感觉，总之这个结论还是很好接受的

知道了这个结论后就比较简单了，我们可以模拟廊桥增加的过程

国内和国外分开处理

通过图片可以很清楚的看出，第\(i\)个廊桥能接纳的飞机，我们只要找到离一个区间右边界最近的左端点就好了

其实这里的处理方法很多，\(O(n),O(nlogn)\) 的都可以过，因为我比较菜，所以写了 \(O(nlogn)\) 的写法

将区间左端点放入集合中，然后按右端点查找，在集合中删去就可以了

将国内和国外分别处理完后，枚举一次就好了

代码实现

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int N,M1,M2,numa[maxn],numb[maxn],ans,q[maxn<<1];
struct air{
	int L,R;
	bool operator <(const air B)const {return this->L<B.L;}
	bool operator ==(const air B)const {return this->L==B.L&&R==B.R;}
}a[maxn],b[maxn],INF,iINF;
set<air> P;
typedef set<air>::iterator it;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int main(){
    N=read();M1=read();M2=read();
    for(int i=1;i<=M1;i++) a[i].L=read(),a[i].R=read(),q[++q[0]]=a[i].L,q[++q[0]]=a[i].R;
    for(int i=1;i<=M2;i++) b[i].L=read(),b[i].R=read(),q[++q[0]]=b[i].L,q[++q[0]]=b[i].R;
    sort(q+1,q+1+q[0]);sort(a+1,a+1+M1);sort(b+1,b+1+M2);
    for(int i=1;i<=M1;i++) a[i].L=lower_bound(q+1,q+1+q[0],a[i].L)-q,a[i].R=lower_bound(q+1,q+1+q[0],a[i].R)-q;
    for(int i=1;i<=M2;i++) b[i].L=lower_bound(q+1,q+1+q[0],b[i].L)-q,b[i].R=lower_bound(q+1,q+1+q[0],b[i].R)-q;
    for(int i=1;i<=M1;i++) P.insert(a[i]); INF.L=0x3f3f3f3f,INF.R=0x3f3f3f3f; P.insert(INF); iINF.L=0; iINF.R=0;
    int i=1;for(int cnt=0;cnt<M1&&!P.empty();i++){
    	it pos=P.begin();int lst=cnt;
    	while(1){
    		air now=*pos;++cnt;now.L=now.R,now.R=0x3f3f3f3f;
			P.erase(pos);pos=P.upper_bound(now);
			if((*pos)==INF)break;
		}
		numa[i]=cnt-lst+numa[i-1];
	}
	for(;i<=N;i++)numa[i]=numa[i-1];
	P.clear();
	for(int i=1;i<=M2;i++) P.insert(b[i]); P.insert(INF);
	i=1;for(int cnt=0;cnt<M2&&!P.empty();i++){
    	it pos=P.begin();int lst=cnt;
    	while(1){
    		air now=*pos;++cnt;now.L=now.R,now.R=0x3f3f3f3f;
			P.erase(pos);pos=P.upper_bound(now);
			air p=*pos;
			if((*pos)==INF)break;
		}
		numb[i]=cnt-lst+numb[i-1];
	}
	for(;i<=N;i++)numb[i]=numb[i-1];
	for(int i=0;i<=N;i++)ans=max(ans,numa[i]+numb[N-i]);
	printf("%d\n",ans);
	return 0;
}

T2

题目链接

括号序列

这个题一看就是区间 DP，应该没有什么问题吧~，不知道也没有其他做法，反正我只能看出是区间 DP

就存在如何定义的问题

~~很显然的~~，我们可以定义 \(F[i][j]\) 表示从 \(i\) 到 \(j\) 的合法方案数

考虑转移，我们发现无非就是几种情况，按照题目的意思写即可

实现我们为了判定一个串是否是 * 的一段，也就是 \(S\) 需要构造一个 \(sum[i]\) 表示 \(i\) 之前的 * 和？的个数，查找一段的时候相减即可

()/(S) 这两种本质上是相同的，只要判断 \(i\) 到 \(j\) 内部是否都是 * ,若是的则\(F[i][j]++\)
(AS) \(F[i][j]+=F[i+1][k]\)，\(k\) 是内部区间的右端点，要保证从 \(k\)到\(j\) 都是 * 方可转移
(SA) 和 (AS) 相同 \(F[i][j]+=F[k][j-1]\) ，\(k\) 是内部区间的左端点，要保证从 \(i\) 到 \(k\) 都是 * 方可转移
(A) 不解释了 \(F[i][j]+=F[i+1][j-1]\) 这个不理解的回炉重造吧
AB/ASB 这个时最难的，我们需要枚举内部两个区间的断点，设\(k1\) 表示内部左区间的右端点，\(k2\) 表示右边区间的右端点，显然需要从 \(k1\) 到 \(k2\) 都是 * 方可转移，\(F[i][j]+=F[i][k1]\times F[k2][j]\)

这里我们发现自己已经写了个 \(O(n^4)\)的DP了，其实还有一些小问题，对于 AB/ASB这种情况会算重

例如 ()()() 这组数据计算 AB/ASB 时被算了两次，一次()+()()，一次 ()()+()，仔细想想是不是

所以我们需要从问题的源头入手，是不是定义除了问题，考虑再加入一个定义：\(G[i][j]\) 表示左端点和右端点必须是一对配对的括号的方案数，例如:(()())是合法的，(())()是不合法的，这个定义很重要

我们发现()()+()这次计算是没有必要的，所以要把它除去，需要修改 5 的转移方程，变成 \(F[i][j]+=G[i][k1]\times F[k2][j]\)，就可以将重复去掉

考虑 \(G[i][j]\) 如何得到，发现对于 1,2,3,4 的情况 \(F\) 和 \(G\) 的转移完全相同，就是 5 的情况是不可能得到 \(G\) 的

好了现在我们的代码已经可以跑 \(n=100\) 左右的数据了，考虑如何优化

瓶颈卡在 5 的转移：\(F[i][j]+=G[i][k1]\times F[k2][j]\)，每个\(k1\) 都要乘上 \(\sum_{\text{合法的k2}} F[k2][j]\) ，显然 \(k2\) 是连续一段的，很容易想到构造一个前缀和，每次只需要乘一次就可以了

此时时间复杂度已经优化到了 \(O(n^3)\) 可以过此题了

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=505;
const LL TT=1e9+7;
int N,K,nxt[maxn];
LL sum[maxn],F[maxn][maxn],G[maxn][maxn],S[maxn];
char s[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline LL min(LL a,LL b){return a<b?a:b;}
inline LL max(LL a,LL b){return a>b?a:b;}
int main(){
	N=read();K=read();int q=0;
	scanf("%s",s+1);
	for(int i=1;i<=N;i++) sum[i]=sum[i-1]+(s[i]=='*'||s[i]=='?');
	nxt[N]=N;for(int i=N-1;i;i--) nxt[i]=(s[i]=='*'||s[i]=='?')?nxt[i+1]:i; 
	for(int i,j,k,k1,k2,L=1;L<N;L++)
	for(i=1;i+L<=N;i++) if(s[i]!='*'&&s[i]!=')'){
		j=i+L;if(s[j]=='('||s[j]=='*')continue;
		(j-i-1==sum[j-1]-sum[i]&&j-i-1<=K)&&((G[i][j]=(F[i][j]+1)%TT)|(F[i][j]=(F[i][j]+1)%TT),0);
		if(j-i-1<2)continue;
		F[i][j]=(F[i][j]+F[i+1][j-1])%TT; G[i][j]=(G[i][j]+F[i+1][j-1])%TT;
		for(k=2;k-1<=K&&i+k<j-1;k++) sum[i+k-1]-sum[i]==k-1&&((F[i][j]=(F[i][j]+F[i+k][j-1])%TT)|(G[i][j]=(G[i][j]+F[i+k][j-1])%TT),0);
		for(k=2;k-1<=K&&i+1<j-k;k++) sum[j-1]-sum[j-k]==k-1&&((F[i][j]=(F[i][j]+F[i+1][j-k])%TT)|(G[i][j]=(G[i][j]+F[i+1][j-k])%TT),0);
		S[i+1]=0;for(k=i+2;k<j;k++) S[k]=(S[k-1]+F[k][j])%TT;
		for(k1=i+1;k1<j-1;k1++) F[i][j]=(F[i][j]+G[i][k1]*(S[min(j-1,min(nxt[k1+1],k1+K+1))]-S[k1]+TT)%TT)%TT;
//		for(k1=i+1;k1<j-1;k1++)
//		for(k2=k1+1;k2<j&&k2-k1-1<=K;k2++){
//			(sum[k2-1]-sum[k1]==k2-k1-1)&&(F[i][j]=(F[i][j]+G[i][k1]*F[k2][j]%TT)%TT,0);
//		}
	}
	printf("%lld\n",F[1][N]);
	return 0;
}

T3

题目描述

回文

这道题的做法也很多，我主要讲我看到最简单的一种，来自于zzj

我们先观察样例，很容易的能得出一个结论：对于一个串来说，外面有\(n\)个是在回文串前面的，里面的\(n\)个是在回文串后面的

在样例中，蓝色的表示前面的回文，绿色的表示后面的回文，蓝色在外面，绿色在里面，和我们的结论一样，~~其实结论也挺显然的~~

所以我们要找出一个在外部和在内部的点模拟就好了

显然的，第一个点肯定是最左边和最右边的任意一个，我们假设最左边的点为第一个被取走的点，它肯定在蓝色的部分，这个数对应的另外一个位置肯定在绿色的部分，于是，我们就可以模拟了

思考，如何模拟匹配的过程

先设四个指针 \(L1,L2,R1,R2\) 表示左边蓝色的右端点，绿色的左端点，绿色的右端点，右边蓝色的右端点，此时的绿色和蓝色的交接位置是不确定的，我们就要模拟出来

观察串是怎么匹配的，在前面的回文上一个位置上为 \(L\) ，那么从左边取，则，\(L1++\)，若从右边，则 \(R2--\) 。在后边的回文上的一个位置上为 \(L\) 则\(L2++\) ，若从右边，则 \(R1--\)

考虑到前面和后面是一样的，我们考虑一起处理，也就是第 \(i\) 位和第 \(N\times 2-i+1\) 位一起处理，我们采用一种逆向思维还原匹配过程，我们就是要找蓝色和绿色交界的位置

若 \(s[L1]=s[L2]\) 则前面的串从左边取，后面的串也从左边取，\(L1++,L2--\)
(此时为什么不是 \(L2++\)，因为我们反向模拟匹配的过程，可以看出还原后绿色向右边移动了一格，也就代表着这个是在后面的回文中出现的，这个思想很重要)，这个时候
若 \(s[L1]=s[R1]\) 则前面的串从左边取，后面的串从右边取，\(L1++,R1++\)
若 \(s[L2]=s[R2]\) 则前面的串从右边取，后面的串从左边取，\(L2--,R2--\)
若 \(s[R1]=s[R2]\) 则前面的串从右边取，后面的串从右边取，\(R1++,R2--\)
若四种方式都不可以匹配，则无解，也挺显然的

我们在匹配的时候已经处理好取的顺序了，输出即可，当然要注意一个小细节，也就是取完后 \(L1\) 会大于 \(L2\) 或者 \(R1\) 大于 \(R2\) ，显然不可能取的。

题目中还需要字典序最小，我们只需要按照 1,2,3,4,的顺序判断能不能取，肯定是最小的，因为 \({L,L}<L,R<R,L<R,R\)

现在已经解决了一遍的问题了，若第一个匹配的数字为右边的，那么同理即可，这里留给大家自己思考

代码实现

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+5;
int N,L1,L2,R1,R2,ans[maxn],a[maxn],ok,T;
char ch[3]="LR";
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
int main(){
	fin>>T;
	while(T--){
		fin>>N;N<<=1;ok=0;
		for(int i=1;i<=N;i++) fin>>a[i];	
		for(int i=2;i<=N;i++) if(a[i]==a[1]){L2=i-1;R1=i+1;break;}; L1=2;R2=N;
		ans[1]=0;ans[N]=0; 
		for(int i=2;i<=(N>>1);i++) {
			if(L1<L2&&a[L1]==a[L2]) L1++,L2--,ans[i]=0,ans[N-i+1]=0;
			else if(L1<=L2&&R1<=R2&&a[L1]==a[R1]) L1++,R1++,ans[i]=0,ans[N-i+1]=1;
			else if(L1<=L2&&R1<=R2&&a[L2]==a[R2]) L2--,R2--,ans[i]=1,ans[N-i+1]=0;
			else if(R1<R2&&a[R1]==a[R2]) R1++,R2--,ans[i]=1,ans[N-i+1]=1;
			else {ok=1;break;}
		}
		if(ok==0) {for(int i=1;i<=N;i++)putchar(ch[ans[i]]);putchar('\n');continue;}
		ok=0;
		for(int i=1;i<N;i++) if(a[i]==a[N]){L2=i-1;R1=i+1;break;}; L1=1;R2=N-1;
		ans[1]=1;ans[N]=0; 
		for(int i=2;i<=(N>>1);i++) {
			if(L1<L2&&a[L1]==a[L2]) L1++,L2--,ans[i]=0,ans[N-i+1]=0;
			else if(L1<=L2&&R1<=R2&&a[L1]==a[R1]) L1++,R1++,ans[i]=0,ans[N-i+1]=1; 
			else if(L1<=L2&&R1<=R2&&a[L2]==a[R2]) L2--,R2--,ans[i]=1,ans[N-i+1]=0;
			else if(R1<R2&&a[R1]==a[R2]) R1++,R2--,ans[i]=1,ans[N-i+1]=1;
			else {ok=1;break;}
		}
		if(ok==0) {for(int i=1;i<=N;i++)putchar(ch[ans[i]]);putchar('\n');continue;}
		putchar('-');putchar('1');putchar('\n');
	}
	return 0;
}

T4

题目链接

交通规划

此题本人只会写 \(k=2\) 时的点，此想法来自于 ix35,%%%，我把它描述的清楚一点

非常显然，当 \(k=2\) 的时候，这是一个最小割问题，不知道的建议右转百度

而这又是一个对偶图问题，关于对偶图的最大流问题可以转化成最短路，这是一种常用套路，推荐一道类似的题目：狼抓兔子

把一个空看成一个节点，把边看成空和空之间的边，重新建图

在转化后，从绿色节点到蓝色节点的距离就是这个图中的最小割

可以怎样理解这个问题，若有一条路径绿色节点和蓝色节点联通，那么这条路径可以将这个图分成两部分，黑白两点分别在两个部分里面

那么 \(k=2\) 的点就解决了

当 \(k!=2\) 的时候，我们也可以采用同样的方法，顺时针看，从黑到白的看成蓝点，从白到黑的看成绿点

我们可以把一排的绿点看成一个超级绿点，蓝点同理，因为一排相同颜色点是等价的，所以绿蓝点时交错出现的，设 \(cnt\) 为块的个数

一条线可以划分出两个区间，将两个区域分开，我们为了使得总的代价最小，肯定希望一条线能划开多个区间或者不要交错，因为交错了的代价肯定更劣

可以感性用上的这张图来理解，但是实际上和这个题目还是有点差异的

我们可以用 \(dij\) 或者 \(spfa\)~~(它已经死了)~~ 来求出 \(g[i][j]\) 表示从第 \(i\) 个块和第 \(j\) 个块分离的最小代价

考虑一个块，必然要和其他不同颜色的块分开，也就是说要单独在一个区域内

观察发现 \(k\) 非常小，就可以使用 \(DP\) 来枚举每种情况，定义 \(F[i][j]\) 表示从第 \(i\) 个串到第 \(j\) 个串能完全匹配的最小代价，初始肯定是 \(F[i][i+1]=g[i][i+1]\)

分为两种情况

将 \(i,j\) 分成两部分分开匹配，也就是 \(F[i][j]=F[i][k]+F[k+1][j]\)
\(i,j\) 两个点匹配，\(F[i][j]=F[i+1][j-1]+g[i][j]\)

最后的答案也就是 \(F[1][cnt]\)

单这里还有一个小问题，就是这个图是一个环，我们要拆成链处理，转移方程都不变，就是处理答案的时候需要扫一遍 \(F[i][i+cnt-1]\) 的最大值即可

代码里面细节巨多，我在实现的时候没有每次去建图，而是用了 \(vector\) 来删掉重复的边，没有设超级绿点和超级蓝点，用了修改边后的第一个点来作为基准点，因为基准点到这一块所有点的距离都是 \(0\)，所以直接拿基准点作为超级绿点/蓝点就可以了

其他细节看代码吧，时间复杂度 \(O(T\times (k^3+knmlognm))\)

代码实现

#pragma GCC optimize(2)
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M,T,K;
int mp[2][505][505],line[2005][3],node[2005][2],id[2005],G[2005][2005],dis[260105],vis[260105],cnt,F[2005][2005],ans;
struct edge{
	int x,w;
	bool operator <(const edge B)const {return w<B.w;}
}hep[260105];
int hep_len;
vector<edge> e[260105];
inline void add_e(int x,int y,int z){
	e[x].push_back((edge){y,z});
}
inline void add_edge(int x,int y,int z){
	e[x].push_back((edge){y,z});e[y].push_back((edge){x,z});
}
struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);return *this;
    }
}fin,fout;
inline int calc(int x,int y){return (x-1)*(M-1)+y;}
bool cmp(int x,int y){return line[x][0]<line[y][0];}
int Nxt(int x){
	return x==(N+M<<1)?1:x+1;
}
void update_edge(int x,int y,int z){
	int flg=0;
	vector<edge>::iterator it=e[x].begin();
	for(;it!=e[x].end();++it){
		if(it->x==y){
			if(it->w==z){flg=1;break;}		
			else {e[x].erase(it);break;}
		}
	}
	if(!flg)add_e(x,y,z);
	it=e[y].begin();flg=0;
	for(;it!=e[y].end();++it){
		if(it->x==x){
			if(it->w==z){flg=1;break;}
			else {e[y].erase(it);break;}
		}
	}
	if(!flg)add_e(y,x,z);
	return ;
}
void put(edge x){
	hep[++hep_len]=x;int son=hep_len;
	while(son>1&&hep[son]<hep[son>>1]) swap(hep[son],hep[son>>1]),son>>=1;
	return ;
}
edge get(){
	edge ret=hep[1];int son,fa=1;hep[1]=hep[hep_len--];
	while((fa<<1)<=hep_len){
		if((fa<<1)>hep_len||hep[fa<<1]<hep[fa<<1|1]) son=fa<<1;else son=fa<<1|1;
		if(hep[son]<hep[fa]) swap(hep[son],hep[fa]),fa=son;else break;
	}
	return ret;
}
void dij(int s){
	memset(dis,63,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[s]=0;edge now;now.x=s;now.w=0;hep_len=0;
	put(now);
	while(hep_len){
		edge tmp=get();
		int x=tmp.x;
		if(vis[x])continue;vis[x]=1;
		for(int i=0,sz=e[x].size();i<sz;++i)
			if(!vis[e[x][i].x]&&dis[e[x][i].x]>dis[x]+e[x][i].w){
				dis[e[x][i].x]=dis[x]+e[x][i].w;
				now.x=e[x][i].x;now.w=dis[e[x][i].x];
				put(now);
			}
	}
	return ;
}
int main(){
	freopen("traffic.in","r",stdin);
	freopen("traffic.out","w",stdout);
	fin>>N>>M>>T;
	for(int i=1;i<N;i++)
	for(int j=1;j<=M;j++) fin>>mp[0][i][j];
	for(int i=1;i<=N;i++)
	for(int j=1;j<M;j++) fin>>mp[1][i][j];
	for(int i=1;i<N;i++)
	for(int j=1;j<M;j++){
		if(i!=N-1){add_edge(calc(i,j),calc(i+1,j),mp[1][i+1][j]);}
		if(j!=M-1){add_edge(calc(i,j),calc(i,j+1),mp[0][i][j+1]);}
	}
	for(int i=1;i<N;i++){
		add_edge(calc(i,1),(N-1)+(M-1<<1)+4+(N-1-i+1)+(N-1)*(M-1),mp[0][i][1]);
		add_edge(calc(i,M-1),(M-1)+2+(i)+(N-1)*(M-1),mp[0][i][M]);
	}
	for(int j=1;j<M;j++){
		add_edge(calc(1,j),j+1+(N-1)*(M-1),mp[1][1][j]);
		add_edge(calc(N-1,j),(N-1)+(M-1)+3+(M-1-j+1)+(N-1)*(M-1),mp[1][N][j]);
	}
	while(T--){
		fin>>K;
		memset(G,63,sizeof G);memset(F,63,sizeof F);ans=0x3f3f3f3f;cnt=0;
		for(int i=1;i<=K;i++) {int l,x,c;fin>>l>>x>>c;line[i][0]=x;line[i][1]=c;id[i]=i;line[i][2]=l;}
		if(K<=1){fout<<0<<'\n';continue;}
		sort(id+1,id+1+K,cmp);
		for(int i=1;i<=K;i++){
			int nx=i+1<=K?i+1:1;
			if(line[id[i]][1]==line[id[nx]][1]){
				for(int j=Nxt(line[id[i]][0]);j!=line[id[nx]][0];j=Nxt(j))update_edge(j+(N-1)*(M-1),Nxt(j)+(N-1)*(M-1),0);
				update_edge(line[id[nx]][0]+(N-1)*(M-1),Nxt(line[id[nx]][0])+(N-1)*(M-1),line[id[nx]][2]);
			}
			else{
				cnt++;
				node[cnt][0]=Nxt(line[id[i]][0])+(N-1)*(M-1);node[cnt][1]=line[id[i]][1];
				for(int j=Nxt(line[id[i]][0]);j!=line[id[nx]][0];j=Nxt(j))update_edge(j+(N-1)*(M-1),Nxt(j)+(N-1)*(M-1),0);
				update_edge(line[id[nx]][0]+(N-1)*(M-1),Nxt(line[id[nx]][0])+(N-1)*(M-1),line[id[nx]][2]);
			}
		}
		for(int i=1;i<=cnt;i++) {
			dij(node[i][0]);
			for(int j=1;j<=cnt;j++) if(i!=j) G[i][j]=min(G[i][j],dis[node[j][0]]);
		}
		for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++) G[i+cnt][j]=G[i][j+cnt]=G[i+cnt][j+cnt]=G[i][j];
		for(int i=1;i<(cnt<<1);i++) F[i][i+1]=G[i][i+1];
		for(int L=3;L<cnt;L+=2)
			for(int i=1,j;i+L<=cnt;i++){
				j=i+L;
				for(int k=i+1;k<=j;k+=2)F[i][j]=min(F[i][j],F[i][k]+F[k+1][j]);
				F[i][j]=min(F[i][j],G[i][j]+F[i+1][j-1]);
			}
		for(int i=1;i<=cnt;i++) ans=min(ans,F[i][i+cnt-1]);
		fout<<(ans==0x3f3f3f3f?0:ans)<<'\n';
	}
	return 0;
}

码农公寓

在前面的话

T1

题目链接

问题解决

代码实现

T2

题目链接

代码实现

T3

题目描述

代码实现

T4

题目链接

代码实现

相关文章