(100+20+0=120pts)
T1：单调队列优化dp
线性dp，设(f[i])为前(i)个数的最小和((i)被选择)。
显然：
(f[i]=min){(~~f[j]+a[i]~~)}(~~(i>j>i-m)~~),
拆一下：
(f[i]=min){(~f[j]~)}(~)(+)(~)(a[i])(~~(i>j>i-m)~~),
已经很裸了，单调队列维护最小的(f[j]).
(T1のCode)：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N],f[N],mn=INT_MAX,q[N];
int main(){
//freopen("minn.in","r",stdin);
//freopen("minn.out","w",stdout);
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[0]=0;
int l=1,r=1;q[1]=0;
for(int i=1;i<=n;i++){
while(l<=r&&q[l]<i-m)l++;
f[i]=f[q[l]]+a[i];
while(l<=r&&f[q[r]]>=f[i])r--;
q[++r]=i;
}
for(int i=n;i>=n-m+1;i--)mn=min(mn,f[i]);
printf("%d",mn);
return 0;
}
T2:区间dp
设(f[l][r])为(l) ~ (r)中的合法序列方案数,
根据空串序列合法性，所以(f[i][i-1]=1),
最后答案是(f[1][n])。
很容易想到(f[l][r])(=)(sum{f[l][k]+f[k+1][r]}),
其实这个转移方程是错误的，看这组样例：
( ) ( ) ( )
这个样例只有唯一的合法括号序列，可是在上述转移中会出现重复计数。
所以在合并时，如有(A)和(B)两个合法括号序列，我们应保证是形如(A)(~)(~)(()(~)(B)(~)())
所以有
- (f[l][r]+=f[l][k]*f[k+2][r-1]~(~s[k+1]==s[r]~~||~~s[k+1]==?~~||~~s[r]==?))
- (f[l][r]+=f[l][k]*f[k+2][r-1]*3~~(~~s[k+1]==s[r]==?~~)~~)
(T2のCode):
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=205;
const int mod=1e5;
int n;
ll f[N][N];
char s[N];
char ls[3]= {'(','[','{'};
char rs[3]= {')',']','}'};
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=n;i++)f[i][i-1]=1;
for(int len=2;len<=n;len+=2)
for(int l=1;l<=n-len+1;l++){
int r=l+len-1;
for(int k=l-1;k<=r;k++)
for(int t=0;t<3;t++)
if((s[k+1]==ls[t]||s[k+1]=='?')&&(s[r]=='?'||s[r]==rs[t]))
f[l][r]=(f[l][r]+((f[l][k]*f[k+2][r-1])%mod))%mod;
}
printf("%lld",f[1][n]%mod);
return 0;
}
T3:单调队列
其实是最水的一道。。可惜保龄收场。
仔细观察发现解法复杂度与(n<=10^9)的惊人范围无关。
(m<=5 imes10^3),可以搞一个(O(m^2))
思考：一个行李箱通过所有障碍的下限是什么？
当然就是通过最狭窄的地方！
想到这个，我们可以枚举长度，然后单调队列跑一遍，得到宽度，然后计算面积即可。
T3のCode：
#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
const int N=5e3+10;
using namespace std;
int n,m,a[N],b[N],q1[N],q2[N];
ll ans;
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
for(int k=1;k<=m;k++){
int d=k,mn=inf;
int l1=1,r1=0,l2=1,r2=0;
for(int i=1;i<=m;i++){
while(l1<=r1&&i-d>q1[l1])l1++;
while(l1<=r1&&a[q1[r1]]<a[i])r1--;
q1[++r1]=i;
while(l2<=r2&&i-d>q2[l2])l2++;
while(l2<=r2&&b[q2[r2]]<b[i])r2--;
q2[++r2]=i;
if(i>=d)if(n-a[q1[l1]]-b[q2[l2]]<=0)mn=0;
else mn=min(mn,n-a[q1[l1]]-b[q2[l2]]);
}
ans=max(ans,1LL*mn*k);
}
printf("%lld",ans);
return 0;
}