P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个题有点坑，就是说你只能往下挖，可以理解成单项路径。比如1与3之间是1代表1可以到3而3不可以到1。所以我们来思考dp把。怎么写？我们这么想假设1与2，3，4都链接只有这两层，那么我们找到到达2，3，4这三个点的可以挖的地雷数量，然后找到最大的即可。这是针对两层，那三层呢，比如3，4又连接着，5.那么我们接着5从与5链接的3，4选出最大的，而不用关心3，4是怎么转化的。所以我们就有了dp方程了

for(a=2;a<=b;a++) {for(int e=a-1;e>0;e--) {//System.out.println(dp[e]+aa[a]+" "+dp[a]+" "+cunzai[a][e]);if(cunzai[e][a]==1&&dp[a]<dp[e]+aa[a]) {dp[a]=dp[e]+aa[a];qianqu[a]=e;}}}

dp【i】的含义是以i结尾的挖地雷的总值。

注意了，输出路径，我们开个前缀数组，这个数组记录每个点的前缀，最后我们选出最大路径是以那个点结尾，我们不断找他的前缀，直到他的某个前缀是0我们就可以输出x编号

public static void dayin(int a) {if(qianqu[a]!=0) {dayin(qianqu[a]);}System.out.print(a+" ");}}

总答案

import java.awt.FontFormatException;import java.io.BufferedReader; import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.lang.reflect.AnnotatedWildcardType;import java.math.BigInteger;import java.net.DatagramPacket;import java.sql.SQLIntegrityConstraintViolationException;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.HashSet;import java.util.LinkedHashSet;import java.util.LinkedList;import java.util.Map;import java.util.Objects;import java.util.PriorityQueue;import java.util.Scanner;import java.util.Spliterator.OfPrimitive;import java.util.function.IntToDoubleFunction;import java.util.function.LongBinaryOperator;import java.util.TreeMap;import java.util.TreeSet;import javax.management.relation.InvalidRelationTypeException;import javax.print.attribute.standard.JobMessageFromOperator;import javax.print.attribute.standard.JobPriority;import javax.swing.plaf.ColorChooserUI;import javax.swing.table.TableModel;import javax.swing.text.TabSet;import javax.xml.crypto.dsig.spec.DigestMethodParameterSpec;public class Main {public static void main(String[] args) throws IOException {Scanner sc=new Scanner(System.in);BufferedReader br1=new BufferedReader(new InputStreamReader(System.in));PrintWriter pw1=new PrintWriter(System.out);String aString=br1.readLine();int b=Integer.parseInt(aString);cunzai=new int[b+1][b+1];aa=new int[b+1];qianqu=new int[b+1];dp=new int[Integer.parseInt(aString)+1];String[] bStrings=br1.readLine().split(" ");int a;for(a=1;a<=bStrings.length;a++) {dp[a]=Integer.parseInt(bStrings[a-1]);//System.out.println(dp[a]);aa[a]=dp[a];}for(a=1;a<=b-1;a++) {String[] cStrings=br1.readLine().split(" ");int c=0;for(int d=a+1;d<=b;d++) {cunzai[a][d]=Integer.parseInt(cStrings[c]);//System.out.print(cunzai[a][d]+" ");c++;}//System.out.println();}for(a=2;a<=b;a++) {for(int e=a-1;e>0;e--) {//System.out.println(dp[e]+aa[a]+" "+dp[a]+" "+cunzai[a][e]);if(cunzai[e][a]==1&&dp[a]<dp[e]+aa[a]) {dp[a]=dp[e]+aa[a];qianqu[a]=e;}}}int ans=0;int weiba=0;for(a=1;a<=b;a++) {if(ans<dp[a]) {ans=dp[a];weiba=a;}}dayin(weiba);System.out.println();System.out.println(ans);}public static int[] aa;public static int[] dp;public static int[] qianqu;public static int[][] cunzai;public static void dayin(int a) {if(qianqu[a]!=0) {dayin(qianqu[a]);}System.out.print(a+" ");}}