题目描述 在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径 Output K1 K2,……,KV （挖地雷的顺序） MAX （挖地雷的数量）
分析 类似于最长不下降序列的做题方法
#include <iostream>#include <cstdio>using namespace std;int main(){ int n,a[100],b[100][100],f[100],i,j,s,k[100],ans; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i<=n;i++) for (j=i+1;j<=n;j++) scanf("%d",&b[i][j]); for (i=n;i>=1;i--) { for (j=i+1;j<=n;j++) if (f[j]>f[i]&&b[i][j]==1) { f[i]=f[j]; k[i]=j; } f[i]=f[i]+a[i]; } ans=1; for (i=2;i<=n;i++) if (f[ans]<f[i]) ans=i; PRintf("%d ",ans); j=k[ans]; while (j>0) { printf("%d ",j); j=k[j]; } printf("/n"); printf("%d",f[ans]); return 0;}新闻热点
疑难解答
