状态表示,类似于最长上升子序列,以i结尾的可删去j个数字的保留i的答案,求最大值
状态计算,我们可以枚举倒数第二个序列中的数字是谁,i-1到0(0指是前面没有数字),且由于第一个和最后一个处于首尾,可以不用删去,w权值是大于等于0,多一个就是赚到,所以枚举的区间是1~i-1,在这些状态中取最大值进行转移,记倒数第二个数的下标是u,那么u~i之间的数字是被删除了,前u个就需要删除j-(i - u - 1)
个
状态初始化,只有一个数无法构成二维信息,记为0,f[1][0] = 0
,再从2开始,同时由于求最大值,其余元素最小化
状态转移方程为f[i][j] = max(f[i][j], f[u][j - (i - u - 1)] + w[a[u][a[i]]);
// package com.microsoft.exercise;
import java.util.Arrays;
import java.util.Scanner;
/*
* @author milo
*/
public class Main {
private final int N = 210;
private int n, k, m;
private int[] a;
private int[][] w, f;
public Main() {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
m = scanner.nextInt();
a = new int[N];
w = new int[N][N];
f = new int[N][N];
for (int i = 1; i <= m; i++) {
a[i] = scanner.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = scanner.nextInt();
}
}
scanner.close();
}
public static void main(String[] args) {
(new Main()).run();
}
private void run() {
// 看fill函数的源码只能对一维数组进行赋值
for (int i = 0; i < N; i++) {
Arrays.fill(f[i], Integer.MIN_VALUE);
}
f[1][0] = 0;
for (int i = 2; i <= m; i++) {
for (int j = 0; j <= k; j++) {
for (int u = 1; u < i; u++) {
if (j >= i - u - 1) {
f[i][j] = Math.max(f[i][j], f[u][j - (i - u - 1)] + w[a[u]][a[i]]);
}
}
}
}
int res = 0;
for (int i = 0; i <= k; i++) {
res = Math.max(res, f[m][i]);
}
System.out.println(res);
}
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 210;
int n, k, m;
int a[N], w[N][N], f[N][N];
int main() {
cin >> n >> k >> m;
for (int i = 1; i <= m; i ++) {
cin >> a[i];
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j++ ){
cin >> w[i][j];
}
}
memset(f, -0x3f, sizeof f);
f[1][0] = 0;
for (int i = 2; i <= m; i ++) {
for (int j = 0; j <= k; j ++ ) {
for (int u = 1; u < i; u ++ ) {
if (j >= (i - u - 1)) {
f[i][j] = max(f[i][j], f[u][j - (i - u - 1)] + w[a[u]][a[i]]);
}
}
}
}
int res = 0;
for (int i = 0; i <= k; i ++ ) {
res = max(res, f[m][i]);
}
cout << res << endl;
return 0;
}
兄弟有时间填个邀请码hhhhhhhhh(可以得AC币,邀请码在学生认证那填) 我的邀请码是:GUDFH
啥东西