社区讨论

DP做法,请问为什么错了?

P2196[NOIP 1996 提高组] 挖地雷参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mhj45chw
此快照首次捕获于
2025/11/03 20:25
4 个月前
此快照最后确认于
2025/11/03 20:25
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=25;
bool c[N][N];//c[i][j]=1表示i到j有路径 
int a[N],b[N],r[N],dp[N];//以i为结束点的最大地雷数
int ans=0,n,cnt=1; 
void zddls(int s){
	memset(dp,0,sizeof(dp));	
	dp[s]=a[s];
	for(int i=s+1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(c[j][i]){
				if(dp[j]+a[i]>=dp[i]){
					dp[i]=dp[j]+a[i];
					b[i]=j;//记录路径 
				}
			}
		}
	}
	ans=max(ans,dp[n]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			int x;
			cin>>x;
			c[i][j]=x;
		}
	}
	for(int i=1;i<=n;i++){
		zddls(i);
	}
	int x=n,tt=n;
	n--;
	cnt=1;
	while(n-->1){//将记录的路径(逆的)转为正的 
		int t=b[x];
		x=t;
		r[cnt++]=x;//正路径 
	}
	for(int i=cnt-1;i>=1;i--){//输出正路径 
		cout<<r[i]<<' ';
	}
	cout<<tt;//最后一个节点 
	cout<<endl<<ans;
}
输出写得不是很好

回复

0 条回复,欢迎继续交流。

正在加载回复...