关于矩阵转移 DP 的一点疑问
  • 板块学术版
  • 楼主hzx360
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/7/29 23:47
  • 上次更新2023/11/3 06:58:47
查看原帖
关于矩阵转移 DP 的一点疑问
556740
hzx360楼主2023/7/29 23:47

有时候程序莫名运行不出来(就是编译可以过,但exe没输出结果就结束了)。

问了大佬貌似是传参时爆掉了???

各位大佬帮忙看看有什么问题,方便以后注意一下。

比如:P6772 [NOI2020] 美食家 中我的代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=252;
int n,m,T,k,c[N];
int id(int i,int j){return (i-1)*5+j;}
struct festival{int t,x,y;}f[N];
struct frac{
	int a[N][N];
	friend frac operator*(frac A,frac B){
		frac C;
		int all=5*n;
		for(int i=1;i<=all;i++) for(int j=1;j<=all;j++) C.a[i][j]=-1e17;
		for(int i=1;i<=all;i++)
			for(int k=1;k<=all;k++) 
				if(A.a[i][k]>=0) for(int j=1;j<=all;j++) C.a[i][j]=max(C.a[i][j],A.a[i][k]+B.a[k][j]);
		return C;
	}
}ans,Q[31];
bool cmp(festival A,festival B){return A.t<B.t;}
void deal(){
	for(int i=1;i<=5*n;i++) for(int j=1;j<=5*n;j++) Q[0].a[i][j]=ans.a[i][j]=-1e17;
	for(int i=1;i<=n;i++)
		for(int j=1;j<5;j++) Q[0].a[id(i,j)][id(i,j+1)]=0;
}
signed main(){
	
	cin>>n>>m>>T>>k;
	deal();
	for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		Q[0].a[id(x,z)][id(y,1)]=c[y];
	}
	for(int i=1;i<=k;i++) scanf("%lld%lld%lld",&f[i].t,&f[i].x,&f[i].y);
	sort(f+1,f+1+k,cmp);
	f[++k]=(festival){T,0,0};
	for(int i=1;i<=30;i++) Q[i]=Q[i-1]*Q[i-1];
	
	for(int i=1;i<=k;i++){
		int ti=f[i].t-f[i-1].t;
		for(int i=30;i>=0;i--) if(ti&(1<<i)) ans=ans*Q[i];
		if(i==k) break;;
		for(int j=1;j<=n*5;j++) if(ans.a[j][f[i].x]>=0) ans.a[j][f[i].x]+=f[i].y;
	}
	cout<<((ans.a[1][1]+c[1])>=0?(ans.a[1][1]+c[1]):-1);
}
2023/7/29 23:47
加载中...