大连企业公司网站建设,企业网站报价,如何提升网站用户体验,沧州微网网络信息有限公司P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题有点坑#xff0c;就是说你只能往下挖#xff0c;可以理解成单项路径。比如1与3之间是1代表1可以到3而3不可以到1。所以我们来思考dp把。怎么写#xff1f;我们这么想假设1与2#xf…P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这个题有点坑就是说你只能往下挖可以理解成单项路径。比如1与3之间是1代表1可以到3而3不可以到1。所以我们来思考dp把。怎么写我们这么想假设1与234都链接只有这两层那么我们找到到达234这三个点的可以挖的地雷数量然后找到最大的即可。这是针对两层那三层呢比如34又连接着5.那么我们接着5从与5链接的34选出最大的而不用关心34是怎么转化的。所以我们就有了dp方程了
for(a2;ab;a) {for(int ea-1;e0;e--) {//System.out.println(dp[e]aa[a] dp[a] cunzai[a][e]);if(cunzai[e][a]1dp[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 scnew Scanner(System.in);
BufferedReader br1new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1new PrintWriter(System.out);
String aStringbr1.readLine();
int bInteger.parseInt(aString);
cunzainew int[b1][b1];
aanew int[b1];
qianqunew int[b1];
dpnew int[Integer.parseInt(aString)1];
String[] bStringsbr1.readLine().split( );
int a;
for(a1;abStrings.length;a) {dp[a]Integer.parseInt(bStrings[a-1]);//System.out.println(dp[a]);aa[a]dp[a];
}
for(a1;ab-1;a) {String[] cStringsbr1.readLine().split( );int c0;for(int da1;db;d) {cunzai[a][d]Integer.parseInt(cStrings[c]);//System.out.print(cunzai[a][d] );c;}//System.out.println();
}
for(a2;ab;a) {for(int ea-1;e0;e--) {//System.out.println(dp[e]aa[a] dp[a] cunzai[a][e]);if(cunzai[e][a]1dp[a]dp[e]aa[a]) {dp[a]dp[e]aa[a];qianqu[a]e;}}
}
int ans0;
int weiba0;
for(a1;ab;a) {if(ansdp[a]) {ansdp[a];weibaa;}
}
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 );}
}
