峡山网站建设,wordpress模板免费,凡科网多页网站怎样做,简述网站建设和推广评价指标题目链接 好久没有写题了复健一下qwq 题目大意 解题思路
这题目还挺妙的 首先考虑比较正常的dp#xff0c; d p [ i ] [ j ] dp[i][j] dp[i][j] 为前 i i i的长度选 j j j个长度的最大价值#xff0c;那么转移方程是#xff1a; 图片来自#xff1a;图片来源 但是这个是 …题目链接 好久没有写题了复健一下qwq 题目大意 解题思路
这题目还挺妙的 首先考虑比较正常的dp d p [ i ] [ j ] dp[i][j] dp[i][j] 为前 i i i的长度选 j j j个长度的最大价值那么转移方程是 图片来自图片来源 但是这个是 O ( n k 2 ) O(nk^2) O(nk2)无法通过把绝对值展开进行讨论
我们可以看到 d p [ i ] [ j ] dp[i][j] dp[i][j]其实都是由对角线上的 d p dp dp值 几个 a a a, b b b的计算那么我们可以把前面的部分用新的数组维护起来因为都是对角上的数值那么 i − j i-j i−j是固定值那么就是 f [ 0 / 1 / 2 / 3 ] [ i − j ] f[0/1/2/3][i-j] f[0/1/2/3][i−j]里面取最大值 后缀部分然后因为这个虽然是对角线的上值的前 k k k里面的最大值但是其实 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] dp[i][j]dp[i-1][j-1] dp[i][j]dp[i−1][j−1]是一定成立的所以 f [ 0 / 1 / 2 / 3 ] [ i − j ] f[0/1/2/3][i-j] f[0/1/2/3][i−j]只用从 k 1 k1 k1转移就行 f[0][i - j] std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);f[1][i - j] std::max(f[1][i - j], dp[i - 1][j - 1] a[i] - b[i]);f[2][i - j] std::max(f[2][i - j], dp[i - 1][j - 1] - a[i] b[i]);f[3][i - j] std::max(f[3][i - j], dp[i - 1][j - 1] a[i] b[i]);记住f数组要初始化为负无穷不能是0
memset(f,0x80,sizeof(f));整体代码
#include iostream
#include cstring
#include cmath
#include vector
#include algorithm
using namespace std;
const int maxn 3005;
typedef long long ll;
const ll mod 998244353;
int a[maxn], b[maxn];
ll dp[maxn][maxn], f[4][maxn];
int main() {//freopen(1.txt,r,stdin);int T;scanf(%d,T);while(T --) {int n, k;scanf(%d%d,n,k);memset(f,0x80,sizeof(f));// 这个0x80初始化出来是复数 for(int i 1; i n; i) cin a[i];for(int i 1; i n; i) cin b[i]; for(int i 1; i n; i) {for(int j 1; j k j i; j) {dp[i][j] dp[i-1][j];f[0][i - j] std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);f[1][i - j] std::max(f[1][i - j], dp[i - 1][j - 1] a[i] - b[i]);f[2][i - j] std::max(f[2][i - j], dp[i - 1][j - 1] - a[i] b[i]);f[3][i - j] std::max(f[3][i - j], dp[i - 1][j - 1] a[i] b[i]);dp[i][j] std::max(dp[i][j], f[0][i - j] a[i] b[i]);dp[i][j] std::max(dp[i][j], f[1][i - j] a[i] - b[i]);dp[i][j] std::max(dp[i][j], f[2][i - j] - a[i] b[i]);dp[i][j] std::max(dp[i][j], f[3][i - j] - a[i] - b[i]);
// for(int h 1; h j; h) {
// dp[i][j] max(dp[i-h][j-h]abs(a[i]-b[i-h1])abs(a[i-h1]-b[i]),dp[i][j]);
// // printf(%d %d %lld\n,i,j,dp[i][j]);
// }}}printf(%lld\n,dp[n][k]);} return 0;
}上面你可能会疑问这个不是抵消了吗
f[0][i - j] std::max(f[0][i - j], dp[i - 1][j - 1] - a[i] - b[i]);
dp[i][j] std::max(dp[i][j], f[0][i - j] a[i] b[i]);注意其实这里的有个影响是 f [ 0 ] [ i − j ] f[0][i - j] f[0][i−j]是包含了带 k k k的参数 所以要做两次 m a x max max, d p [ i − 1 ] [ j − 1 ] − a [ i ] − b [ i ] dp[i - 1][j - 1] - a[i] - b[i] dp[i−1][j−1]−a[i]−b[i]只是刚好这一层儿而已
