CoderXx

CoderXx
1天前

### 题目描述

1≤N,M≤1000

#### 输入样例:

4 5
acbd
abedc


#### 输出样例：

3


### 算法

##### DP $O(n^2)$

f[i][j]是字符串q的前i个字符和字符串p的前j个字符中公共子序列的最大值。

#### Java 代码

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();int m = sc.nextInt();
String p = " " + sc.next(), q = " " + sc.next();
int[][] f = new int[n + 1][m + 1];

for(int i = 1; i<=n; i++){
for(int j = 1; j<=m; j++){
f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
if(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
}
}
System.out.println(f[n][m]);
}
}


CoderXx
1天前
import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();int m = sc.nextInt();
String p = " " + sc.next(), q = " " + sc.next();
int[][] f = new int[n + 1][m + 1];

for(int i = 1; i<=n; i++){
for(int j = 1; j<=m; j++){
f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
if(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
}
}
System.out.println(f[n][m]);
}
}


CoderXx
1天前
import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] s = new int[n+1];
int[][] f = new int[n+1][n+1];
for(int i = 1; i <= n; i++){
s[i] = sc.nextInt();//s存储的是前缀和
s[i] += s[i-1];
}

for(int len = 2; len <= n; len++){//划出区间
for(int i = 1; i + len - 1 <= n; i++){
int l = i, r = i + len - 1;
f[l][r] = 10000000;
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]);
}
}
}
System.out.println(f[1][n]);
}
}


CoderXx
1天前
import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();int m = sc.nextInt();
String p = " " + sc.next(), q = " " + sc.next();
int[][] f = new int[n + 1][m + 1];

for(int i = 1; i<=n; i++){
for(int j = 1; j<=m; j++){
f[i][j] = Math.max(f[i][j-1], f[i-1][j]);
if(p.charAt(i) == q.charAt(j)) f[i][j] = Math.max(f[i][j], f[i-1][j-1] + 1);
}
}
System.out.println(f[n][m]);
}
}


CoderXx
2天前
import java.util.*;
public class Main{

public static void main(String[] args){
//f[i]表示以a[i]结尾的最长上升子序列。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n+1], f = new int[n+1];
for(int i = 1; i <= n; i++)
a[i] = sc.nextInt();

for(int i = 1; i <= n; i++){
f[i] = 1;//若a[i]结尾的递增子序列都没有，前面的数字都比a[i]大那么f[i]等于1，a[i]以自己为结尾.
for(int j = 1; j < i; j++){
if(a[j] < a[i]){
f[i] = Math.max(f[i], f[j] + 1);
}
}
}

int res = 0;
for(int i = 0; i <= n; i++) res = Math.max(res, f[i]);//求完f[i]后在f[i]中寻找一个最大值。

System.out.println(res);
}
}


CoderXx
3天前
//这里填你的代码^^
import java.util.*;
public class Main{

private static final int N = 510;

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[N][N], f = new int[N][N];

for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
nums[i][j] = sc.nextInt();
}
}

for(int i = 0; i <= n; i++){
for(int j = 0; j <= i + 1; j++){
f[i][j] = Integer.MIN_VALUE;
}
}

f[1][1] = nums[1][1];

for(int i = 2; i<=n; i++)
for(int j = 1; j <= i; j++)
f[i][j] = Math.max(f[i-1][j-1], f[i-1][j] )+ nums[i][j];

int res = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) res = Math.max(res, f[n][i]);
System.out.println(res);
}
}


CoderXx
3天前
import java.util.*;

class Main{

private static final int N = 110;

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
int[][] v = new int[N][N], w = new int [N][N];
int[] s = new int[N], f = new int[N];

for(int i = 1; i <= n; i++){
s[i] = sc.nextInt();
for(int j = 1; j <= s[i]; j++){
v[i][j] = sc.nextInt();
w[i][j] = sc.nextInt();
}
}

for(int i = 1; i <= n; i++){
for(int j = m; j >= 0; j--){
for(int k = 1; k <= s[i]; k++){
if(j >= v[i][k])f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}

System.out.println(f[m]);
}

}


CoderXx
3天前
import java.util.*;
public class Main {

private static final int N = 25000;

public static void main(String[] args) {
System.out.println(multiplePacketProblems());
}

private static int multiplePacketProblems(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[N], w = new int[N];
int[] f = new int[N];
int cnt = 0;
for (int i = 1; i <= n; i++) {
int a = sc.nextInt(), b = sc.nextInt(), s = sc.nextInt(), k = 1;
while( k <= s){
cnt++;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if(s > 0){
cnt++;
v[cnt] = a * s;
w[cnt] = b * s;
}
}

for(int i = 1; i <= cnt; i++)
for(int j = m; j >= v[i]; j--)
f[j] = Math.max(f[j], f[j-v[i]] + w[i]);

return f[m];
}
}


CoderXx
4天前
import java.util.*;
public class Main {

public static void main(String[] args) {
System.out.println(multiplePacketProblems());
}

private static int multiplePacketProblems(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[n+1], w = new int[n+1], s = new int[n+1];
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}

for(int i = 1; i <= n; i++){
for (int j = 0; j <= m; j++){
for(int k = 0; k <= s[i] && k * v[i] <= j; k ++){
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-k*v[i]] + k * w[i]);
}
}
}
return dp[n][m];
}
}


CoderXx
4天前
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
System.out.println(completePacketProblem());
}

private static int completePacketProblem(){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[n+1], w = new int[n+1];
int[][] dp = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}

for(int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]] + w[i]);
}
}
return dp[n][m];
}
}