期望得分：100+100+30=230
实际得分：
正解：
枚举最高的位，这一位m是1但实际用了0
然后剩余的低位肯定是 正数就用1，负数用0
考场思路：数位DP
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; typedef long long LL; #define N 100001 int a[N]; char s[N]; LL dp[N][]; void read(int &x)
{
x=; int f=; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=f;
} LL dfs(int dep,int num,bool lim)
{
if(!dep) return ;
if(!lim && dp[dep][num]!=-) return dp[dep][num];
int up= lim ? s[dep]-'' : ; LL res=;
res=dfs(dep-,,lim && ==s[dep]-'');
if(up) res=max(res,a[dep]+dfs(dep-,,lim && ==s[dep]-''));
if(!lim) dp[dep][num]=res;
return res;
} int main()
{
freopen("maximum.in","r",stdin);
freopen("maximum.out","w",stdout);
int n;
read(n);
for(int i=;i<=n;i++) read(a[i]);
scanf("%s",s+);
memset(dp,-,sizeof(dp));
cout<<dfs(n,,);
}
二分+DP
dp[i] 表示 到第i个数， 在满足条件(任意两个相邻的数，差<=mid)的情况下，并且i没有被改变，最少改变多少数字。
状态转移： dp[i]=dp[k]+(i-k-1) k=0~i-1 表示 k+1~i-1 都被改变了
转移条件：mid*(k-i)>=abs(a[k]-a[i]) k~i这段区间能满足条件
只管修改了多少个数，至于改成了什么，不关心
最大的差最小，就是让数均匀分布，那么二分最大的差，条件就是差*个数>= | 区间右边-左边 |
也就是假设区间左右端点都不改变，而区间内部都改变
区间内部都改变是最差的情况，他会随着区间左端点的移动而变小
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 1001 int dp[N],a[N]; int n,k; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool check(int mid)
{
for(int i=;i<=n;i++)
{
dp[i]=i-;
for(int j=;j<i;j++)
if(abs(a[i]-a[j])<=mid*(i-j)) dp[i]=min(dp[i],dp[j]+i-j-);
}
int mi=dp[n];
for(int i=;i<n;i++) mi=min(mi,dp[i]+n-i);
return mi<=k;
} int main()
{
freopen("minimum.in","r",stdin);
freopen("minimum.out","w",stdout);
read(n); read(k);
for(int i=;i<=n;i++) read(a[i]);
int l=,r=,mid,ans;
for(int i=;i<=n;i++) r=max(r,abs(a[i]-a[i-]));
ans=r;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d",ans);
}
将A看做+y，B看做-x，问题转化为 在[L,R] 内 求 最长和为0的区间
记录 前缀和 a[i] ，若 a[v]-a[u]=0 ，则 [u+1,v] 为 一个和为0的区间
将所有的前缀和离散化为c[i]
pos[i] 表示 当前 离散化 后为i的数 第一次 出现在pos[i]
假设当前在位置j，
若 pos[c[j]] 之前被更新过了，那么 [ pos[c[j]],j ] 就是一个 和为0的区间 ，且是以j为右端点的最长的
若没有被更新，用j更新pos[c[j]]
将 字符串分为根号n 块
用上述方法在n*根号n 时间 内 预处理完 这三个数组：
two[i][j] i，j <= 根号n ，第i个块到第j个块之间 和为0 的最长区间
l[i][j] i <= 根号 n ，j <=n，区间[ 第i块的第一个位置,j ] 和为0的最长区间
r[i][j] i <= 根号 n ，j <=n，区间[ j+1，第i块的最后一个位置 ] 和为0的最长区间
对于 一个询问 L,R
由四部分更新
设L所在块为bL，R所在块为bR
① 最优解 在 [L,R] 完整的块内 即 two[bL+1][bR-1]
② 最优解的左端点 不在[L,R] 完整块内，右端点在[L,R]完整块内 即 r[bR-1][L-1]
③ 最优解的左端点 在[L,R]完整块内，右端点不在[L,R] 完整块内，即l[bL+1][R]
④ 最优解 的左右端点都不在[L,R] 完整块内 ，
那么 用上面的方法 枚举 左边不在完整块内的部分，枚举右边不在完整块内的部分，O（2*根号n） 求解
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; #define N 100001 char s[N]; int a[N],b[N],c[N]; int two[][],l[][N],r[][N]; int pos[N]; int use[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int getgcd(int a,int b) { return !b ? a : getgcd(b,a%b); } int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int n,x,y;
read(n); read(x); read(y);
int g=getgcd(x,y); x/=g; y/=g;
scanf("%s",s+);
for(int i=;i<=n;++i)
{
if(s[i]=='A') a[i]=a[i-]+y;
else a[i]=a[i-]-x;
b[i]=a[i];
}
sort(b+,b+n+);
int tot=unique(b+,b+n+)-b-;
for(int i=;i<=n;++i) c[i]=lower_bound(b+,b+tot+,a[i])-b;
int siz=sqrt(n),mx,m=siz;
int cnt=;
memset(pos,-,sizeof(pos));
for(int i=,k=;i<=n;i+=siz,++k)
{
mx=cnt=;
for(int j=i,kk=k;j<=n;j+=siz,++kk)
{
for(int h=;h<=siz;++h)
{
if(pos[c[j+h-]]!=-) mx=max(mx,j+h--pos[c[j+h-]]);
else pos[c[j+h-]]=j+h-;
use[++cnt]=c[j+h-];
}
two[k][kk]=mx;
}
for(int i=;i<=cnt;++i) pos[use[i]]=-;
}
for(int i=,k=;i<=n;i+=siz,++k)
{
cnt=;
for(int j=i;j<=n;++j)
{
if(pos[c[j]]!=-) l[k][j]=max(l[k][j-],j-pos[c[j]]);
else l[k][j]=l[k][j-],pos[c[j]]=j;
use[++cnt]=c[j];
}
for(int j=;j<=cnt;++j) pos[use[j]]=-;
}
for(int i=siz,k=;i<=n;i+=siz,++k)
{
cnt=;
for(int j=i;j>=;--j)
{
if(pos[c[j]]!=-) r[k][j]=max(r[k][j+],pos[c[j]]-j);
else r[k][j]=r[k][j+],pos[c[j]]=j;
use[++cnt]=c[j];
}
for(int j=;j<=cnt;++j) pos[use[j]]=-;
}
int q;
read(q);
int L,R; int bL,bR; int ans;
while(q--)
{
read(L); read(R);
bL=(L-)/siz+; bR=(R-)/siz+;
ans=;
if(bR-bL<)
{
cnt=;
for(int i=L-;i<=R;++i)
{
if(pos[c[i]]!=-) ans=max(ans,i-pos[c[i]]);
else pos[c[i]]=i;
use[++cnt]=c[i];
}
for(int i=;i<=cnt;++i) pos[use[i]]=-;
}
else
{
ans=two[bL+][bR-];
ans=max(ans,r[bR-][L-]);
ans=max(ans,l[bL+][R]);
cnt=;
int t=bL*siz;
for(int i=L-;i<=t;++i)
{
if(pos[c[i]]!=-) ans=max(ans,i-pos[c[i]]);
else pos[c[i]]=i;
use[++cnt]=c[i];
}
for(int i=(bR-)*siz+;i<=R;++i)
{
if(pos[c[i]]!=-) ans=max(ans,i-pos[c[i]]);
else pos[c[i]]=i;
use[++cnt]=c[i];
}
for(int i=;i<=cnt;++i) pos[use[i]]=-;
}
cout<<ans<<'\n';
}
}