题解 P9980

题意：

一排点，可以从前往后连单向边（无重边），给定每两个点之间路径数，求总连边数。

思路：

我们要求的就是对于每两个点

i,j

满足

i<j

，它们之间到底有没有单向边。设

t_{i,j}=0

表示没有单向边，

t_{i,j}=1

表示有单向边。

考虑两点之间路径数是如何被计算出来的。设

G(i,j)

表示

i,j

之间的路径数（

i<j

），我们有：

G(i,j)=\sum_{k=i+1}^{j-1}t_{i,k}\times G(k,j)+t_{i,j}

即：考虑

i,j

之间的一个点

k

，若

i,k

有连边，则答案增加

G(k,j)

。最后再加上

i,j

间直连的个数。

因此我们就有了递推式子，可以参考其它题解，这里不重复给出。

程序如下：

CPP

#include<cstdio>
#include<cmath>
using namespace std;
const int N=755;
int n,ans;
char ch[N];
bool a[N][N],rt[N][N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%s",ch+1);
		for(int j=i+1;j<=n;j++)
			if(ch[j-i]=='1')
				a[i][j]=1;
	}
	for(int len=1;len<=n;len++){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			rt[i][j]=a[i][j];
			for(int k=i+1;k<j;k++)rt[i][j]^=(rt[i][k]&a[k][j]);
		}
	}
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			ans+=rt[i][j];
	printf("%d\n",ans);
	return 0;
}

THE END

USACO 2024 Dec RP++.

文章操作

题意：

思路：

程序如下：

THE END

相关推荐

评论

题解 P9980