6747

Amaryllis_

yxc的小迷妹
lorenzo_必上岸
ekatsim
y_yy

Kirito_

0000sz

题目描述

blablabla

JAVA 代码


import java.io.IOException;

public class Main {
static int N = 310;
static int[] a = new int[N];
static int[][] f = new int[N][N];//f[i][j]表示将所有[i-j]合并成一堆的方案集合，取最小值
public static void main(String[] args) throws IOException {
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(s[i-1]);
a[i] += a[i-1];//区间和
}
//套路:先枚举区间长度
for (int len = 2; len <= n; len++) {//从2开始
for (int i = 1; i + len -1 <= n; i++) {//枚举左区间，减一是左区间最多到n-1，然后右区间留一个
int j = i + len -1;
f[i][j] = (int) 1e8;
for (int k = i; k < j; k++) {//k最多到j-1，
f[i][j] = Math.min(f[i][j],f[i][k] + f[k+1][j] + a[j] - a[i-1]);
}
}
}
System.out.println(f[1][n]);
}
}



题目描述

blablabla

JAVA 代码


import java.io.IOException;

public class Main {
static int N = 1010;
static String[] p = new String[N];//n个字符串
static String q[] = new String[N];//m个字符串
static int[][] f = new int[N+10][N+10];////所有将a[1-i]变成b[1-j]的操作方式
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
for (int i = 1; i <= n; i++) {
}

for (int i = 1; i <= m; i++) {
int res = 0;
char[] a = q[i].split(" ")[0].toCharArray();
int limit = Integer.parseInt(q[i].split(" ")[1]);
for (int j = 1; j <= n; j++) {//判断有多少个字符串和当前的字符串能够在限制的次数下匹配
char[] b = p[j].toCharArray();
if(limit_distance(a,b) <= limit){
res++;
}
}
System.out.println(res);
}

}
static int limit_distance(char[] a,char[] b){//a是询问的字符串，b是给定的字符串
for (int i = 0; i <= b.length; i++) f[0][i] = i;
for (int i = 0; i <= a.length; i++) f[i][0] = i;

for (int i = 1; i <= a.length; i++) {
for (int j = 1; j <= b.length; j++) {
f[i][j] = Math.min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i-1]==b[j-1]) f[i][j] = Math.min(f[i][j],f[i-1][j-1]);
else f[i][j] = Math.min(f[i][j],f[i-1][j-1]+1);
}
}
return f[a.length][b.length];
}
}



题目描述

blablabla

JAVA代码


import java.io.IOException;

public class Main {
/**
* 状态计算分为三种情况
* 删除：在删掉i之前a[i-1]和b[j]是相同的，用f[i-1][j]表示a[i-1]变成b[j]的操作方式的最小值，f[i-1][j]+1表示加一步删除的操作
* 增加：在添加j之前a[i]和b[j-1]是相同的，用f[i][j-1]表示a[i]变成b[j-1]的操作方式的最小值，f[i][j-1]+1表示加一步添加的操作
* 改：在添加i之前a[i-1]和b[j-1]是相同的，用f[i-1][j-1]表示a[i-1]变成b[j-1]的操作方式的最小值，如果相同a[i]和b[j]相同，f[i][j]不用，如果不同，f[i][j]=f[i-1][j-1]+1;
* */
static int N = 1010;
static char[] a = new char[N];
static char[] b = new char[N];
static int [][] f = new int[N][N];//所有将a[1-i]变成b[1-j]的操作方式的最小值
public static void main(String[] args) throws IOException {
for (int i = 1; i <= n; i++) {
a[i] = A.toCharArray()[i-1];
}
for (int i = 1; i <= m; i++) {
b[i] = B.toCharArray()[i-1];
}
//        System.out.println(n+"   "+m);
//初始化
for (int i = 1; i <= m; i++) f[0][i] = i; //把a的前0个字母变成b的前i个字母，添加i次
for (int i = 1; i <= n; i++) f[i][0] = i; //把a的前i个字母变成b的前0个字母，删除i次

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i] == b[j]) f[i][j] = Math.min(f[i][j],f[i-1][j-1]);
else f[i][j] = Math.min(f[i-1][j-1]+1,f[i][j]);
}
}
System.out.println(f[n][m]);
}
}



题目描述

blablabla

JAVA 代码


import java.io.IOException;

public class Main {
static int N = 1010;
static char[] a = new char[N];
static char[] b = new char[N];
static int[][] f = new int[N][N];//所有a[1-i]和b[1-j]的公共子序列的集合的最大值
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
for (int i = 1; i <= A.length(); i++) {
a[i] = A.toCharArray()[i-1];
}
for (int i = 1; i <=B.length() ; i++) {
b[i] = B.toCharArray()[i-1];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.max(f[i-1][j],f[i][j-1]);//不相等的时候，两个字符一定有一个可以抛弃，可以对f[i-1][j],f[i][j-1]两种状态取max。
if(a[i] == b[j]) f[i][j] = Math.max( f[i][j] , f[i-1][j-1]+1);//如果相同 f[i][j] = f[i - 1][j - 1] + 1
}
}
System.out.println(f[n][m]);
}
}



题目描述

blablabla

JAVA 代码


import java.io.IOException;

public class Main {
//进来一个数q[i]时，通过二分在f[]中找到最大的小于q[i]的数，就能够将qi接到该数的后面，即更新f[r + 1] = q[i]
static int N = 100010;
static int q[] = new int[N];
static int f[] = new int[N];//所有不同长度上升子序列的结尾的最小值
public static void main(String[] args) throws IOException {
for (int i = 1; i <= n; i++) {
q[i] = Integer.parseInt(s[i-1]);
}
int len = 0;//当前的最大长度，也就是f[]里面的最大个数,初始是0
f[1] = (int) -2e9;//

for (int i = 1; i <= n; i++) {
int l =0;int r = len;
while (l < r){ //二分 找小于某个数的最大的数
int mid = l+r+1 >> 1;
if(f[mid] < q[i]) l = mid;//f[] 是找找小于q[i]的最大的数,如果f[mid] < q[i]，说明还没找到距离q[i]的最近的最大的数，继续向右找
else r = mid-1;
}
len = Math.max(len , r+1); // r找的是可以接在哪个数的后面，也就是目前哪个数的比它小的数里面的最大值，找到以后加1
f[r + 1] = q[i];//r+1长度的上升子序列 的 结尾的最小值 是 q[i]
}
System.out.println(len);
}
}



题目描述

blablabla

JAVA 代码



import java.io.IOException;

public class Main{
static int INF = 0x3f3f3f3f;
static int N = 510;
static int p[][] = new int[N][N];
static int f[][] = new int[N][N];
public static void main(String[] args) throws IOException {
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)
{
f[i][j] = -INF;
}
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
p[i][j] = Integer.parseInt(s[j-1]);
f[i][j] = Math.max(f[i-1][j-1],f[i-1][j])+p[i][j];
}
}
int res = -INF;
for (int i = 1; i <= n; i++) {
res = Math.max(res,f[n][i]);
}
System.out.println(res);

}
}



题目描述

blablabla

JAVA 代码


import java.io.IOException;

public class Main {
static int N = 110;
static int[][] v = new int[N][N];
static int[][] w = new int[N][N];
static int[] s = new int[N];
static int[][] f = new int[N][N];//只从前i组选，且总体积不大于j的所有选法
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s1[0]);
int V = Integer.parseInt(s1[1]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= s[i]; j++) {
v[i][j] = Integer.parseInt(s2[0]);
w[i][j] = Integer.parseInt(s2[1]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
//不选第i组物品
f[i][j] = f[i-1][j];
for (int k = 1; k <= s[i]; k++) {//第i组物品有几个物品
//选第i组物品，选哪个
if(j >= v[i][k]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i][k]] + w[i][k]);
}
}
}
System.out.println(f[n][V]);
}
}



题目描述

blablabla

JAVA代码



import java.io.IOException;

public class Main {
/**
* 1.为什么不能用完全背包问题的思路去解决
* 因为完全背包没有物品个数限制，所以只要体积够用就可以一直选，没有最后一项。
* 完全背包最后那一项体积是刚好用完了的，而多重背包最后那一项之后还有体积没用完，所以多重背包的式子后面还可以多减一项，而完全背包就不行了。
* 2.优化方法及代码
*
*
* 3.01背包问题的优化写法
* https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
* @param args
*/
static int N = 12010;
static int M = 2010;
static int v[] = new int[N];
static int w[] = new int[N];//
static int f[] = new int[M];//体积小于M
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(s1[0]);//物品种数
int m = Integer.parseInt(s1[1]);//背包容积。
int cnt = 0;//分组的组别
for (int i = 1; i <= n; i++) {
int a = Integer.parseInt(ss[0]);
int b = Integer.parseInt(ss[1]);
int s = Integer.parseInt(ss[2]);
int k = 1;//组别里面的个数
/**
* 第一个组1
* 第二个组2
* 第三个组4
* 第四个组8
* ...
*/
while (k <= s){
cnt++;//组别数先增加
v[cnt] = a*k;//这个组的整体体积
w[cnt] = b*k;//这个组的整体价值
s -= k;//s减小
k *= 2;//组别数成倍增加
}
//剩余的最后一组
if(s>0){
cnt++;
v[cnt] = a*s;
w[cnt] = b*s;
}
}

n = cnt;//我们每次要枚举的是组数
//优化后的01背包
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}