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+" ");}
}
)
