import java.io.*;
import java.util.Arrays;
public class Main{
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String [] s = br.readLine().split(” “);
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int [][]matrix = new int [n+1][n+1];
int []dist = new int [n+1];
boolean [] isD = new boolean[n+1];
for(int i=1; i<=n; i) Arrays.fill(matrix[i], 100000);
for(int i=0;i<m;i){
s = br.readLine().split(” “);
int a = Integer.parseInt(s[0]);
int b = Integer.parseInt(s[1]);
int c = Integer.parseInt(s[2]);
matrix[a][b] = Math.min(c, matrix[a][b]);
//System.out.println(matrix[a][b]);
}
System.out.println(dijskral(matrix,dist,isD,n));
}
public static int dijskral(int[][]matrix,int []dist,boolean[] isD,int N){
Arrays.fill(dist,Integer.MAX_VALUE);
dist[1] = 0;
//每次循环确定一个
for(int i =1;i<=N;i){
int t =-1;
for(int j =1;j<=N;j){
if(!isD[j]&& (t==-1||dist[j]<dist[t])){
t = j;
}
}
isD[t] = true;
for(int k=1;k<=N;k++){
dist[k] = Math.min(dist[k],dist[t]+matrix[t][k]);
//System.out.println(dist[k]);
}
}
if(dist[N]==100000){return -1;}
return dist[N];
}
}

`import java.io.;
import java.util.;

public class Main{
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String [] s = br.readLine().split(” “);
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);

    int [][] arr = new int [n][m];
    List<List<Point>> reach = new ArrayList<List<Point>>();
    for(int i=0;i<n;i++){
        s = br.readLine().split(" ");
        List<Point> list = new ArrayList<>();
        reach.add(list);
        for(int j=0;j<m;j++){
            Point point = new Point(i,j);
            list.add(point);
            arr[i][j] = Integer.parseInt(s[j]);
        }
    }

    //记录到达状态得矩阵
    Queue <Point> queue = new LinkedList<>();
    reach.get(0).get(0).count = 0;
    queue.offer(reach.get(0).get(0));
    while(!queue.isEmpty()){
        Point p = queue.poll();
        int x = p.x;
        int y = p.y;
        if(x>0&&reach.get(x-1).get(y).count==-1&&arr[x-1][y]!=1){
            reach.get(x-1).get(y).count = reach.get(x).get(y).count+1;
            queue.offer(reach.get(x-1).get(y));
        }
         if(y>0&&reach.get(x).get(y-1).count==-1&&arr[x][y-1]!=1){
            reach.get(x).get(y-1).count = reach.get(x).get(y).count+1;
            queue.offer(reach.get(x).get(y-1));
        }
         if(x+1<n&&reach.get(x+1).get(y).count==-1&&arr[x+1][y]!=1){
            reach.get(x+1).get(y).count = reach.get(x).get(y).count+1;
            queue.offer(reach.get(x+1).get(y));
        }
         if(y+1<m&&reach.get(x).get(y+1).count==-1&&arr[x][y+1]!=1){
             reach.get(x).get(y+1).count = reach.get(x).get(y).count+1;
             queue.offer(reach.get(x).get(y+1));
        }
    }
    System.out.println(reach.get(n-1).get(m-1).count);
}

}
class Point{
int x;
int y;
int count = -1;
public Point(int x , int y){
this.x = x;
this.y = y;
}
}`

`import java.io.*;

class Main{
static int num ;
static boolean [] column = new boolean[10];
static boolean [] across = new boolean[20];
static boolean [] reacross = new boolean[20];
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String [][] path = new String[n+1][n+1];
for(int i=0;i<n;i){
for(int j=0;j<n;j){
path[i][j] = “.”;
}
}
num =n;
dfs(1,path);
}
//k表示了行数
public static void dfs(int k , String [][] path){
//当遍历来到最后一层
if(k==num+1){
for(int i=0;i<num;i){
for(int j=0;j<num;j){
System.out.print(path[i][j]);
}
System.out.println(“”);
}
System.out.println();
return;
}
for(int i=1;i<=num;i++){
if(!column[i]&&!across[k+i-1]&&!reacross[num+k-i]){
path[k-1][i-1] = “Q”;
column[i] = true;
across[k+i-1] = true;
reacross[num+k-i] = true;
dfs(k+1,path);
column[i] =false;
across[k+i-1] = false;
reacross[num+k-i] = false;
path[k-1][i-1] = “.”;
}
}
}
}
`

题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

C++ 代码

import java.io.*;
import java.util.Arrays;

class Main{
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String [] s = br.readLine().split(” “);
int [] sum = new int [n+1];
for(int i=0;i<n;i++){
int arr = Integer.parseInt(s[i]);
sum[i+1] = sum[i]+arr;
}

    int [][] dp = new int [n+1][n+1];
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int l=i;
            int r = l+len-1;
            dp[l][r] = Integer.MAX_VALUE-100;
            for(int k =l ; k<r ; k++){
                dp[l][r] = Math.min( dp[l][r] , dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    System.out.println(dp[1][n]);
}

}

import java.io.*;
import java.util.Arrays;
class Main{
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String [] s = br.readLine().split(” “);
int [] sum = new int [n+1];
for(int i=0;i<n;i){
int arr = Integer.parseInt(s[i]);
sum[i+1] = sum[i]+arr;
}
int [][] dp = new int [n+1][n+1];
for(int len=2;len<=n;len){
for(int i=1;i+len-1<=n;i){
int l=i;
int r = l+len-1;
dp[l][r] = Integer.MAX_VALUE-100;
for(int k =l ; k<r ; k){
dp[l][r] = Math.min( dp[l][r] , dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
}
}
}
System.out.println(dp[1][n]);
}
}