P3287 SCOI2014 方伯伯的玉米田 Sol

题目链接。

感觉强度还好的紫。

不难发现每一次操作肯定到最后，这样子一定不劣。

考虑最基础的DP设计，定义 \(dp[i][j]\) 表示 \(i\) 节点，使用 \(j\) 次操作所留下的最大玉米数量。

考虑直接转移，发现我们需要同时满足 \(a_j+k_j\le a_i+k_i,k_j \le k_i\) 才能进行转移。这样的转移相当坐牢，因为考虑优化。

不放将其上到二维平面，那么就是要维护单点修改，区间最大值了，可以使用二维树状数组解决。

Code

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
const int N = 1e4 + 10,M = 500 + 5000 + 10;
int n,k;
int a[N],mx;
int tre[5600][560];
int lowbit(int x){return x & (-x);
}
void update(int x,int y,int val){for(int i=x;i<=mx+k;i+=lowbit(i))for(int j=y;j<=k+1;j+=lowbit(j))tre[i][j] = max(tre[i][j],val);
}
int query(int x,int y){int ans = 0;for(int i=x;i;i-=lowbit(i))for(int j=y;j;j-=lowbit(j))ans = max(ans,tre[i][j]);return ans;
}
int main(){IOS;cin >> n >> k;for(int i=1;i<=n;i++){cin >> a[i];mx = max(mx,a[i]);}int ans = 0;for(int i=1;i<=n;i++){for(int j=k;j>=0;j--){int res = query(a[i]+j,j+1) + 1;update(a[i]+j,j+1,res);ans = max(ans,res);}}cout << ans;return 0;
}