1354

RyanMoriarty
C艹
Pipipapi
Gamkiu
ysl0310
lxm

123go

Q_83
трава

warnder

wangdong

import java.io.*;

public class Main {
static int n;
static final int mod = (int) Math.pow(10, 9) + 7;
static int[][] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
f = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) f[i][0] = 1;//表示当容量为0，我每次一件物品都不选，就是一种方案

for (int i = 1; i <= n; i++) {//遍历每件物品，1-n,每件物品体积就是i
for (int j = 1; j <= n; j++) {//遍历背包容量,1-n
if (i > j) {
f[i][j] = f[i - 1][j] % mod;//表示当物品体积超过容量j时，只能不选
} else {
f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;//求出所有情况的和（优化后的写法）
}
}
}
writer.write(f[n][n] + "");
writer.flush();
writer.close();
reader.close();

}
}


import java.io.*;

public class Main {
static int n;
static final int mod = (int) Math.pow(10, 9) + 7;
static int[][] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
f = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) f[i][0] = 1;//表示当容量为0，我每次一件物品都不选，就是一种方案

for (int i = 1; i <= n; i++) {//遍历每件物品，1-n,每件物品体积就是i
for (int j = 1; j <= n; j++) {//遍历背包容量,1-n
if (i > j) {
f[i][j] = f[i - 1][j] % mod;//表示当物品体积超过容量j时，只能不选
} else {
f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;//求出所有情况的和（优化后的写法）
}
}
}
writer.write(f[n][n] + "");
writer.flush();
writer.close();
reader.close();

}
}


import java.io.*;

public class Main {
static int n;
static int[] s;//s是前缀和
static int[][] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
s = new int[n + 1];
f = new int[n + 1][n + 1];
String[] str = reader.readLine().split(" ");
for (int i = 1; i <= n; i++) {
s[i] = Integer.parseInt(str[i - 1]);
s[i] += s[i - 1];
}

//区间dp问题的两层外循环一般是：第一层是区间长度N,第二层是从区间左端点开始，同时保证区间右端点在区间范围内
for (int len = 2; len <= n; len++) {//长度为1，表示已经是1堆，消耗体力为0，不用枚举
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;//从i开始，长度为len时,j的下标
f[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {//接着枚举能将i-j分为两堆的分割点，并取消耗体力最小的选法
f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}

}

//则最终f[1][n]为我们要求的答案，因为表示是将1到n合为一堆的体力消耗最小值，即就是题目问我们的问题
writer.write(f[1][n] + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int n;
static int[] s;//s是前缀和
static int[][] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
s = new int[n + 1];
f = new int[n + 1][n + 1];
String[] str = reader.readLine().split(" ");
for (int i = 1; i <= n; i++) {
s[i] = Integer.parseInt(str[i - 1]);
s[i] += s[i - 1];
}

//区间dp问题的两层外循环一般是：第一层是区间长度N,第二层是从区间左端点开始，同时保证区间右端点在区间范围内
for (int len = 2; len <= n; len++) {//长度为1，表示已经是1堆，消耗体力为0，不用枚举
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;//从i开始，长度为len时,j的下标
f[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {//接着枚举能将i-j分为两堆的分割点，并取消耗体力最小的选法
f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}

}

//则最终f[1][n]为我们要求的答案，因为表示是将1到n合为一堆的体力消耗最小值，即就是题目问我们的问题
writer.write(f[1][n] + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int n, m;
static int[][] f;
static char[] a;
static char[] b;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
a = reader.readLine().toCharArray();
m = Integer.parseInt(reader.readLine());
b = reader.readLine().toCharArray();
f = new int[n + 1][m + 1];

//初始化f[0][k] 和 f[k][0]
for (int i = 0; i <= n; i++) f[i][0] = i;//表示将有i个字符的A变为空的B，最少是通过删除i步得到
for (int i = 0; i <= m; i++) f[0][i] = i;//表示将空的A变为有i个字符的B，最少是通过增加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 - 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);
}
}
}

writer.write(f[n][m] + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int n, m;
static int[][] f;
static char[] a;
static char[] b;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
a = reader.readLine().toCharArray();
m = Integer.parseInt(reader.readLine());
b = reader.readLine().toCharArray();
f = new int[n + 1][m + 1];

//初始化f[0][k] 和 f[k][0]
for (int i = 0; i <= n; i++) f[i][0] = i;//表示将有i个字符的A变为空的B，最少是通过删除i步得到
for (int i = 0; i <= m; i++) f[0][i] = i;//表示将空的A变为有i个字符的B，最少是通过增加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 - 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);
}
}
}

writer.write(f[n][m] + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int n, m;
static int[][] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
String[] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
f = new int[n + 1][m + 1];
char[] a = reader.readLine().toCharArray();
char[] b = reader.readLine().toCharArray();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
writer.write(f[n][m] + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int n, m;
static int[][] f;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
String[] str = reader.readLine().split(" ");
n = Integer.parseInt(str[0]);
m = Integer.parseInt(str[1]);
f = new int[n + 1][m + 1];
char[] a = reader.readLine().toCharArray();
char[] b = reader.readLine().toCharArray();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) {
f[i][j] = f[i - 1][j - 1] + 1;
} else {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
}
}
}
writer.write(f[n][m] + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int[] a;
static int[] f;
static int n;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
a = new int[n];
f = new int[n+1];
int len = 0;
String[] str = reader.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(str[i]);
}
for (int i = 0; i < n; i++) {
int l = 0;
int r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (f[mid] < a[i]) l = mid; //如果中间值小于a[i],则继续往右找，直到找到第一个大于等于a[i]的停止（找左边小于a[i]的第一个最大值）
else r = mid - 1;
}
len = Math.max(len, r + 1);//更新单调递增序列的最大长度
f[r + 1] = a[i];//将a[i]接到找到第一个小于它的最大值，即左大
}

writer.write(len + "");
writer.flush();
writer.close();
reader.close();
}
}


import java.io.*;

public class Main {
static int[] a;
static int[] f;
static int n;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

public static void main(String[] args) throws IOException {
n = Integer.parseInt(reader.readLine());
a = new int[n];
f = new int[n+1];
int len = 0;
String[] str = reader.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(str[i]);
}
for (int i = 0; i < n; i++) {
int l = 0;
int r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (f[mid] < a[i]) l = mid; //如果中间值小于a[i],则继续往右找，直到找到第一个大于等于a[i]的停止（找左边小于a[i]的第一个最大值）
else r = mid - 1;
}
len = Math.max(len, r + 1);//更新单调递增序列的最大长度
f[r + 1] = a[i];//将a[i]接到找到第一个小于它的最大值，即左大
}

writer.write(len + "");
writer.flush();
writer.close();
reader.close();
}
}