网站服务器是指什么,深圳网站建设加盟,阳江人才网,网站建设优化服务特色正题
luogu 3287 金牌导航 数据结构优化DP-5 题目大意
有n个玉米#xff0c;给出高度#xff0c;你可以选择一个区间#xff0c;使这个区间的玉米高度1#xff0c;你可以进行k次这样的操作#xff0c;查询你操作完后最长不下降子序列最大值 代码
对于选择区间[l,r]给出高度你可以选择一个区间使这个区间的玉米高度1你可以进行k次这样的操作查询你操作完后最长不下降子序列最大值 代码
对于选择区间[l,r]如果同时把[r1,n]也选进去因为是最长不下降子序列所以让后面更高满足需求所以我们把[r1,n]也选进去所以每次选择区间都是[i,n]
设fi,jf_{i,j}fi,j为前i个玉米总共选择j次的最长不下降子序列因为每次选择区间都是[i,n]所以i被选择了j次那么有
fi,jmaxki,c⩽j,akc⩽aij(fk,c1)f_{i,j}\max_{ki, c\leqslant j,a_kc\leqslant a_ij}(f_{k,c}1)fi,jki,c⩽j,akc⩽aijmax(fk,c1)
对于c⩽j,akc⩽aijc\leqslant j,a_kc\leqslant a_ijc⩽j,akc⩽aij可以建一个二维树状数组维护每次找满足条件的 代码
#include cstdio
#include cstring
#include iostream
#include algorithm
#define ll long long
#define N 10010
using namespace std;
int n, k, a[N], c[510][N];
void add(int x, int y, int z) {for (x; x k 1; x x -x)//因为有0而树状数组计算不了0所以要1for (int jy y; jy 5500; jy jy -jy) c[x][jy] max(c[x][jy], z);return;
}
int ask(int x, int y) {int g 0;for (x; x; x - x -x)for (int jy y; jy; jy - jy -jy) g max(g, c[x][jy]);return g;
}
int main() {scanf(%d%d, n, k);for (int i 1; i n; i) scanf(%d, a[i]);for (int i 1; i n; i)for (int j k; j 0; --j)add(j, a[i] j, ask(j, a[i] j) 1);printf(%d, ask(k, 5500));return 0;
}
