欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

第一章动态规划（十）

程序员文章站 2022-07-13 11:30:07
...

区间DP

例题：1068.环形石子合并
第一章动态规划（十）
类比 282.合并石子

import java.util.Scanner;

public class Main {
	static int INF = Integer.MAX_VALUE >> 1;
	static int N = 410;//开两倍
    static int n;
    static int[] s = new int[N];
    static int[] w = new int[N];
    static int[][] f = new int[N][N];
    static int[][] g = new int[N][N];
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
			w[i] = sc.nextInt();
			w[i + n] = w[i];
		}
        sc.close();
        //前缀和
        for (int i = 1; i <= n * 2; i++) {
			s[i] = s[i - 1] + w[i];
		}
        //初始化
        for (int i = 0;i < f.length;i++) {
			for (int j = 0; j < f[i].length; j++) {
				f[i][j] = INF;
			}
		}
        for (int i = 0;i < g.length;i++) {
			for (int j = 0; j < g[i].length; j++) {
				g[i][j] = -INF;
			}
		}
        for (int len = 1; len <= n; len++) {
			for (int l = 1; l + len - 1 <= n * 2; l++) {
				int r = l + len - 1;
				if (len == 1) {
					f[l][r] = 0;
					g[l][r] = 0;
				}else {
					for (int k = l; k < r; k++) {
						f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
						g[l][r] = Math.max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
					}
				}
			}
		}
        int minV = INF;
        int maxV = -INF;
        for (int i = 1; i <= n; i++) {
			minV = Math.min(minV, f[i][i + n - 1]);
			maxV = Math.max(maxV, g[i][i + n - 1]);
		}
        System.out.println(minV);
        System.out.println(maxV);
    }
}

例题：320. 能量项链
第一章动态规划（十）
第一章动态规划（十）

import java.util.Scanner;

public class Main {
    static int N = 210;
    static int n;
    static int[] w = new int[N];
    static int[] s = new int[N];
    static int[][] f = new int[N][N];
    static int INF = 0x3f3f3f3f;
    
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1;i <= n;i++) {
            int x = sc.nextInt();
            w[i] = x;
            w[i + n] = x;   
        }
        sc.close();
        
        for (int len = 3;len <= n + 1;len ++) {
            for (int L = 1;L + len - 1 <= n * 2;L ++) {
                int R = L + len - 1;
                f[L][R] = -INF;
                for (int k = L + 1;k < R;k ++) {
                    f[L][R] = Math.max(f[L][R], f[L][k] + f[k][R] + w[L] * w[k] * w[R]); 
                }
            }
        }
        int res = 0;
        for (int i = 1;i <= n;i++) {
            res = Math.max(res, f[i][i + n]);
        }
        System.out.println(res);
    }
}

例题：凸多边形的划分
原题链接
【题目描述】
给定一个具有 N个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 N−2个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。
【输入】
输入第一行为顶点数 N
第二行依次为顶点 1至顶点 N的权值。
【输出】
输出仅一行，为这些三角形顶点的权值乘积和的最小值。
【输入样例】
5
121 122 123 245 231
【输出样例】
12214884
【提示】
数据范围与提示：
对于 100% 的数据，有 N≤50，每个点权值小于 109 。
————————————————————————————————————————————————————
需要高精度
第一章动态规划（十）
代码有错

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 55;
    static int M = 35;
    static int INF = (int) 1e9;
    static int n;
    static int[] w = new int[N];
    static long[][][] f = new long[N][N][M];
    static long[] c = new long[M];
    
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
			w[i] = sc.nextInt();
		}
        sc.close();
        
        long[] tmp = new long[M];
        for (int len = 3; len <= n; len++) {
			for (int l = 1; l + len - 1 <= n; l++) {
				int r = l + len - 1;
				f[l][r][M - 1] = 1;
				for (int k = l + 1; k < r; k++) {
					Arrays.fill(tmp, 0);
					tmp[0] = w[l];
					mul(tmp, w[k]);
					mul(tmp, w[r]);
					add(tmp, f[l][k]);
					add(tmp, f[k][r]);
					if (cmp(f[l][r], tmp) > 0) System.arraycopy(f[l][r], 0, tmp, 0, tmp.length);
				}
			}
		}
        print(f[1][n]);
    }
    
    private static void add(long[] a, long[] b) {
    	Arrays.fill(c, 0);
    	for (int i = 0, t = 0; i < M; i++) {
			t += a[i] + b[i];
			c[i] = t % 10;
			t /= 10;
		}
    	System.arraycopy(a, 0, c, 0, c.length);
    }
    
    private static void mul(long[] a, long b) {
    	Arrays.fill(c, 0);
    	long t = 0;
    	for (int i = 0; i < M; i++) {
			t += a[i] * b;
			c[i] = t % 10;
			t /= 10;
		}
    	System.arraycopy(a, 0, c, 0, c.length);
    }
    
    private static int cmp(long[] a, long[] b) {
    	for (int i = M - 1; i >= 0; i--) {
			if (a[i] > b[i]) {
				return 1;
			}else if (a[i] < b[i]){
				return -1;
			}
		}
    	return 0;
    }
    
    private static void print(long[] a) {
    	int k = M - 1;
    	while(k > 0 && a[k] == 0) k--;
    	while(k >= 0) System.out.print(a[k--]);
    	System.out.println();
    }
}

例题：479. 加分二叉树
第一章动态规划（十）
第一章动态规划（十）

import java.util.Scanner;

public class Main {
    static int N = 50;
    static int n;
    static int[] w = new int[N];
    static int[][] f = new int[N][N];
    static int[][] root = new int[N][N];
    
    public static void main(String[] args)  {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
			w[i] = sc.nextInt();
		}
        sc.close();
        
        for (int len = 1; len <= n; len ++ ) {
            for (int l = 1; l + len - 1 <= n; l ++ ) {
                int r = l + len - 1;
                for (int k = l; k <= r; k ++ ) {
                    int left = k == l ? 1 : f[l][k - 1];
                    int right = k == r ? 1 : f[k + 1][r];
                    int score = left * right + w[k];
                    if (l == r) score = w[k];
                    if (f[l][r] < score) {
                        f[l][r] = score;
                        root[l][r] = k;
                    }
                }
            }
		}
        System.out.printf("%d\n", f[1][n]);
        dfs(1, n);
        System.out.println();
    }
    
    private static void dfs(int l, int r) {
        if (l > r) return;
        int k = root[l][r];
        System.out.printf("%d ", k);
        dfs(l, k - 1);
        dfs(k + 1, r);
    }
}

例题：321. 棋盘分割
第一章动态规划（十）

f[x1][y1][x2][y2][k] : 将矩阵(x1,y1)->(x2,y2)分割成k个矩阵的最小方差
记忆化搜索：

import java.util.*;

class Main{
	static int n, m = 8;
	static double X, INF = 1e9;
	static int[][] s;
	static double[][][][][] f;

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		s = new int[m+1][m+1];
		for(int i = 1; i <= m; i++){
			for(int j = 1; j <= m; j++){
				s[i][j] = sc.nextInt();
				s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
			}
		}
		sc.close();
		
		X = (double) s[m][m] / n;
		f = new double[m + 1][m + 1][m + 1][m + 1][n + 1];
		for(int i1 = 0; i1 <= m; i1++){
			for(int j1 = 0; j1 <= m; j1++){
				for(int i2 = 0; i2 <= m; i2++){
					for(int j2 = 0; j2 <= m; j2++){
						for(int k = 0; k <= n; k++){
							f[i1][j1][i2][j2][k] = -INF;
						}
					}
				}
			}
		}
		System.out.println(String.format("%.3f", Math.sqrt(dp(1, 1, m, m, n))));
	}
	private static double dp(int x1, int y1, int x2, int y2, int k){
		double t = f[x1][y1][x2][y2][k];
		if(t >= 0) return t;
		if(k == 1){
			t = get(x1, y1, x2, y2);
			f[x1][y1][x2][y2][k] = t;
			return t;
		}
		t = INF;
		for(int i = x1; i < x2; i++){
			t = Math.min(t, dp(x1, y1, i, y2, k - 1) + get(i+1, y1, x2, y2));
			t = Math.min(t, dp(i+1, y1, x2, y2, k-1) + get(x1, y1, i, y2));
		}
		for(int j = y1; j < y2; j++){
			t = Math.min(t, dp(x1, y1, x2, j, k-1) + get(x1, j+1, x2, y2));
			t = Math.min(t, dp(x1, j+1, x2, y2, k-1) + get(x1, y1, x2, j));
		}
		f[x1][y1][x2][y2][k] = t;
		return t;
	}
	private static double get(int x1, int y1, int x2, int y2){
		double sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] - X;
		return (double) (sum * sum) / n;
	}
}
相关标签： 算法提高课

上一篇： 洛-校门外的树

下一篇： 第一章动态规划（十三）

推荐阅读