cf946D 背包+区间dp 好题
/*
先预处理出每行消去i个1后可以的到的最小时间：
先求每行的前缀和，枚举左端点和右端点，消去的1 cost=tot-sum[r]+sum[l-1],区间长度=r-l+1
time[cost]=min(time[cost],len)
然后再进行行间处理：
就是n行删k个，转化为n组物品，然后总代价是k
分组背包做一下完事
dp[i][j]表示到第i行删了j个的最少上课时间
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 505
int n,m,K,mp[maxn][maxn];
int t[maxn][maxn],sum[maxn][maxn],dp[maxn][maxn]; void init(){
memset(t,0x3f,sizeof t);
for(int i=;i<=n;i++){
t[i][sum[i][m]]=;//全删完的情况
for(int l=;l<=m;l++)
for(int r=l;r<=m;r++){
int len=r-l+;
int cost=sum[i][m]-(sum[i][r]-sum[i][l-]);
t[i][cost]=min(t[i][cost],r-l+);
}
}
/*for(int i=1;i<=n;i++){
for(int j=0;j<=sum[i][m];j++)
cout<<t[i][j]<<" ";
puts("");
}*/
}
int main(){
cin>>n>>m>>K;
char ch;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
cin>>ch;
mp[i][j]=ch-'';
sum[i][j]=sum[i][j-]+mp[i][j];
}
init(); memset(dp,0x3f,sizeof dp);
for(int j=;j<=K;j++)dp[][j]=t[][j];
for(int i=;i<=n;i++)
for(int j=;j<=K;j++)
for(int c=;c<=j;c++)
dp[i][j]=min(dp[i][j],dp[i-][j-c]+t[i][c]); int ans=0x3f3f3f3f;
for(int j=;j<=K;j++)
ans=min(ans,dp[n][j]);
cout<<ans<<endl;
}
cf893d 线段树区间更新，可以傻逼贪心做
/*
在每个0之前都要变成非负，这个非负数要尽量大。。
先求前缀和数组，从左往右扫，找到第一个在0前的负值点，将其提高到允许的最大值x，然后后面统一+x
线段树维护区间最大前缀和，然后从左往右扫，扫到ai=0时进行询问
如果该点前缀和小于0那么将其提高，提高的上限lim=d-后面区间最大前缀和，如果lim+当前值<0，那么不可行
反之不进行操作
对前缀和先判一下。。
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define ll long long
ll ans,n,d,a[maxn],sum[maxn],flag; #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
ll Max[maxn<<],lazy[maxn<<];
void pushup(int rt){Max[rt]=max(Max[rt<<],Max[rt<<|]);}
void pushdown(int rt){
if(lazy[rt]){
lazy[rt<<]+=lazy[rt];lazy[rt<<|]+=lazy[rt];
Max[rt<<]+=lazy[rt];Max[rt<<|]+=lazy[rt];
lazy[rt]=;
}
}
void build(int l,int r,int rt){
if(l==r){Max[rt]=sum[l];return;}
int m=l+r>>;
build(lson);build(rson);
pushup(rt);
}
void update(int L,int R,ll val,int l,int r,int rt){
if(L<=l &&R>=r){lazy[rt]+=val;Max[rt]+=val;return;}
int m=l+r>>;
pushdown(rt);
if(L<=m)update(L,R,val,lson);
if(R>m)update(L,R,val,rson);
pushup(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l && R>=r)return Max[rt];
pushdown(rt);
int m=l+r>>;ll res=-0x3f3f3f3f;
if(L<=m)res=query(L,R,lson);
if(R>m)res=max(res,query(L,R,rson));
return res;
}
int main(){
cin>>n>>d;
for(int i=;i<=n;i++)cin>>a[i];
for(int i=;i<=n;i++){sum[i]=sum[i-]+a[i];if(sum[i]>d)flag=;}
if(flag){
puts("-1");
return ;
}
build(,n,);
for(int i=;i<=n;i++){
if(a[i]==){
int tmp=query(i,i,,n,);
if(tmp>=)continue;
else{
int Max=query(i,n,,n,);
int lim=d-Max;
if(tmp+lim< || flag){
puts("-1");
return ;
}
else {
update(i,n,lim,,n,);
ans++;
}
}
}
}
cout<<ans<<endl;
}
cf797E 复杂度均摊成根号n级别，新题
#include<bits/stdc++.h>
using namespace std;
#define maxn 120005
int q,n,a[maxn];
int dp[maxn][];//dp[i][j]表示在位置i(p=i)，k=j时的跳跃步数，dp[i][j]=dp[i+a[i]+j][j]+1
void init(){
for(int j=;j<=;j++)
for(int i=n;i>=;i--){
if(i+a[i]+j>n)dp[i][j]=;
else dp[i][j]=dp[i+a[i]+j][j]+;
}
}
int main(){
cin>>n;
for(int i=;i<=n;i++)cin>>a[i];
init(); cin>>q;
while(q--){
int ans=,p,k;
cin>>p>>k;
if(k<=){
cout<<dp[p][k]<<'\n';
continue;
}
while(p<=n){
p+=a[p]+k;
ans++;
}
cout<<ans<<'\n';
}
}
cf46D 线段树区间合并沙比提。。一个vector下标搞错弄了好久
#include<bits/stdc++.h>
using namespace std;
#define maxn 120005
int q,n,a[maxn];
int dp[maxn][];//dp[i][j]表示在位置i(p=i)，k=j时的跳跃步数，dp[i][j]=dp[i+a[i]+j][j]+1
void init(){
for(int j=;j<=;j++)
for(int i=n;i>=;i--){
if(i+a[i]+j>n)dp[i][j]=;
else dp[i][j]=dp[i+a[i]+j][j]+;
}
}
int main(){
cin>>n;
for(int i=;i<=n;i++)cin>>a[i];
init(); cin>>q;
while(q--){
int ans=,p,k;
cin>>p>>k;
if(k<=){
cout<<dp[p][k]<<'\n';
continue;
}
while(p<=n){
p+=a[p]+k;
ans++;
}
cout<<ans<<'\n';
}
}