强行做做试试看吧。
http://acm.hust.edu.cn/vjudge/contest/124721#overview
密码:mytrain
C - 柱爷与咸鱼神功
一个简单01背包。
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const LL mod=1000000007; int v[5005]; int t[5005]; int p[5005]; int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif int n,m; cin>>m>>n; for(int i=0;i<n;i++) { scanf("%d%d",&t[i],&p[i]); } for(int i=0;i<n;i++) { for(int j=m;j>=t[i];j--) { v[j]=max(v[j],v[j-t[i]]+p[i]); } } cout<<v[m]<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
E - 柱爷与最大区间和
题意从一个区间中选取两个不相邻的区间使得这两个区间和最大.
dp[i][j]表示前j个数分成i份时且选择最后一个数的最大和，dp[i][j]=max(dp[i][j-1]+num[j],dp[i-1][k]+num[j]) (0<k<j-1)
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <queue> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const LL mod=1000000007; int dp[3][500005]; int pre[500005]; int num[500005]; int main() { #ifdef local freopen("in","r",stdin); // freopen("out","w",stdout); int _time=clock(); #endif int n; cin>>n; for(int i=1;i<=n;i++) { sd(num[i]); pre[i-1]=-inf; } dp[1][0]=-inf; for(int i=1;i<=n;i++) { dp[1][i]=max(dp[1][i-1]+num[i],num[i]); } pre[1]=dp[1][1]; for(int i=1;i<=n;i++) { pre[i]=max(pre[i-1],dp[1][i]); } dp[2][1]=-inf; for(int j=2;j<=n;j++) { dp[2][j]=max(dp[2][j-1],pre[j-2])+num[j]; } int ans=-inf; for(int i=1;i<=n;i++) ans=max(dp[2][i],ans); cout<<ans<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
Q - 柱爷的下凡
01背包，打表预处理一下，肯定第一个硬币是1的，枚举另两个
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const LL mod=1000000007; int ans1[205],ans2[205]; void init() { ans1[1]=2,ans2[1]=3; ans1[2]=2,ans2[2]=3; ans1[3]=2,ans2[3]=3; ans1[4]=2,ans2[4]=3; ans1[5]=2,ans2[5]=3; ans1[6]=2,ans2[6]=3; ans1[7]=2,ans2[7]=5; ans1[8]=3,ans2[8]=4; ans1[9]=3,ans2[9]=4; ans1[10]=2,ans2[10]=5; ans1[11]=2,ans2[11]=5; ans1[12]=4,ans2[12]=6; ans1[13]=4,ans2[13]=6; ans1[14]=4,ans2[14]=6; ans1[15]=3,ans2[15]=7; ans1[16]=4,ans2[16]=6; ans1[17]=3,ans2[17]=7; ans1[18]=4,ans2[18]=6; ans1[19]=3,ans2[19]=8; ans1[20]=3,ans2[20]=8; ans1[21]=5,ans2[21]=7; ans1[22]=4,ans2[22]=9; ans1[23]=4,ans2[23]=9; ans1[24]=5,ans2[24]=8; ans1[25]=5,ans2[25]=8; ans1[26]=5,ans2[26]=8; ans1[27]=5,ans2[27]=8; ans1[28]=4,ans2[28]=9; ans1[29]=5,ans2[29]=8; ans1[30]=5,ans2[30]=8; ans1[31]=4,ans2[31]=9; ans1[32]=5,ans2[32]=8; ans1[33]=5,ans2[33]=8; ans1[34]=7,ans2[34]=11; ans1[35]=7,ans2[35]=11; ans1[36]=7,ans2[36]=11; ans1[37]=5,ans2[37]=12; ans1[38]=5,ans2[38]=12; ans1[39]=5,ans2[39]=12; ans1[40]=7,ans2[40]=11; ans1[41]=5,ans2[41]=12; ans1[42]=5,ans2[42]=12; ans1[43]=5,ans2[43]=12; ans1[44]=7,ans2[44]=11; ans1[45]=7,ans2[45]=11; ans1[46]=7,ans2[46]=11; ans1[47]=7,ans2[47]=11; ans1[48]=6,ans2[48]=14; ans1[49]=6,ans2[49]=14; ans1[50]=6,ans2[50]=14; ans1[51]=6,ans2[51]=14; ans1[52]=8,ans2[52]=13; ans1[53]=8,ans2[53]=13; ans1[54]=8,ans2[54]=13; ans1[55]=8,ans2[55]=13; ans1[56]=8,ans2[56]=13; ans1[57]=6,ans2[57]=14; ans1[58]=6,ans2[58]=14; ans1[59]=6,ans2[59]=14; ans1[60]=8,ans2[60]=13; ans1[61]=8,ans2[61]=13; ans1[62]=6,ans2[62]=14; ans1[63]=6,ans2[63]=14; ans1[64]=6,ans2[64]=14; ans1[65]=8,ans2[65]=13; ans1[66]=8,ans2[66]=13; ans1[67]=8,ans2[67]=13; ans1[68]=8,ans2[68]=13; ans1[69]=7,ans2[69]=17; ans1[70]=7,ans2[70]=17; ans1[71]=7,ans2[71]=17; ans1[72]=7,ans2[72]=17; ans1[73]=7,ans2[73]=17; ans1[74]=9,ans2[74]=14; ans1[75]=7,ans2[75]=17; ans1[76]=7,ans2[76]=17; ans1[77]=7,ans2[77]=17; ans1[78]=7,ans2[78]=17; ans1[79]=7,ans2[79]=17; ans1[80]=10,ans2[80]=16; ans1[81]=10,ans2[81]=16; ans1[82]=10,ans2[82]=16; ans1[83]=10,ans2[83]=16; ans1[84]=8,ans2[84]=19; ans1[85]=8,ans2[85]=19; ans1[86]=8,ans2[86]=19; ans1[87]=8,ans2[87]=19; ans1[88]=6,ans2[88]=20; ans1[89]=10,ans2[89]=17; ans1[90]=11,ans2[90]=15; ans1[91]=11,ans2[91]=15; ans1[92]=11,ans2[92]=15; ans1[93]=11,ans2[93]=15; ans1[94]=11,ans2[94]=18; ans1[95]=11,ans2[95]=18; ans1[96]=12,ans2[96]=19; ans1[97]=12,ans2[97]=19; ans1[98]=12,ans2[98]=19; ans1[99]=12,ans2[99]=19; ans1[100]=12,ans2[100]=19; ans1[101]=12,ans2[101]=19; ans1[102]=12,ans2[102]=19; ans1[103]=12,ans2[103]=19; ans1[104]=12,ans2[104]=19; ans1[105]=12,ans2[105]=19; ans1[106]=12,ans2[106]=19; ans1[107]=12,ans2[107]=19; ans1[108]=12,ans2[108]=19; ans1[109]=12,ans2[109]=19; ans1[110]=12,ans2[110]=19; ans1[111]=13,ans2[111]=18; ans1[112]=12,ans2[112]=19; ans1[113]=12,ans2[113]=19; ans1[114]=12,ans2[114]=19; ans1[115]=12,ans2[115]=19; ans1[116]=12,ans2[116]=19; ans1[117]=12,ans2[117]=19; ans1[118]=12,ans2[118]=19; ans1[119]=12,ans2[119]=19; ans1[120]=12,ans2[120]=19; ans1[121]=12,ans2[121]=19; ans1[122]=12,ans2[122]=19; ans1[123]=7,ans2[123]=23; ans1[124]=7,ans2[124]=23; ans1[125]=8,ans2[125]=27; ans1[126]=8,ans2[126]=27; ans1[127]=8,ans2[127]=27; ans1[128]=9,ans2[128]=23; ans1[129]=9,ans2[129]=23; ans1[130]=9,ans2[130]=23; ans1[131]=9,ans2[131]=30; ans1[132]=9,ans2[132]=30; ans1[133]=14,ans2[133]=22; ans1[134]=14,ans2[134]=22; ans1[135]=10,ans2[135]=26; ans1[136]=14,ans2[136]=22; ans1[137]=8,ans2[137]=27; ans1[138]=8,ans2[138]=27; ans1[139]=14,ans2[139]=22; ans1[140]=8,ans2[140]=27; ans1[141]=8,ans2[141]=27; ans1[142]=10,ans2[142]=26; ans1[143]=8,ans2[143]=27; ans1[144]=8,ans2[144]=27; ans1[145]=8,ans2[145]=27; ans1[146]=8,ans2[146]=27; ans1[147]=8,ans2[147]=27; ans1[148]=8,ans2[148]=27; ans1[149]=8,ans2[149]=27; ans1[150]=8,ans2[150]=27; ans1[151]=8,ans2[151]=27; ans1[152]=8,ans2[152]=27; ans1[153]=9,ans2[153]=30; ans1[154]=9,ans2[154]=30; ans1[155]=9,ans2[155]=30; ans1[156]=9,ans2[156]=30; ans1[157]=9,ans2[157]=30; ans1[158]=9,ans2[158]=30; ans1[159]=9,ans2[159]=30; ans1[160]=9,ans2[160]=30; ans1[161]=9,ans2[161]=30; ans1[162]=9,ans2[162]=30; ans1[163]=9,ans2[163]=30; ans1[164]=9,ans2[164]=30; ans1[165]=9,ans2[165]=30; ans1[166]=9,ans2[166]=30; ans1[167]=9,ans2[167]=30; ans1[168]=9,ans2[168]=30; ans1[169]=9,ans2[169]=30; ans1[170]=9,ans2[170]=30; ans1[171]=9,ans2[171]=30; ans1[172]=12,ans2[172]=31; ans1[173]=12,ans2[173]=31; ans1[174]=12,ans2[174]=31; ans1[175]=12,ans2[175]=31; ans1[176]=10,ans2[176]=34; ans1[177]=10,ans2[177]=34; ans1[178]=10,ans2[178]=34; ans1[179]=10,ans2[179]=33; ans1[180]=10,ans2[180]=34; ans1[181]=10,ans2[181]=34; ans1[182]=10,ans2[182]=34; ans1[183]=10,ans2[183]=34; ans1[184]=10,ans2[184]=34; ans1[185]=10,ans2[185]=34; ans1[186]=10,ans2[186]=34; ans1[187]=10,ans2[187]=34; ans1[188]=12,ans2[188]=31; ans1[189]=12,ans2[189]=31; ans1[190]=12,ans2[190]=31; ans1[191]=12,ans2[191]=31; ans1[192]=12,ans2[192]=31; ans1[193]=12,ans2[193]=31; ans1[194]=12,ans2[194]=31; ans1[195]=12,ans2[195]=31; ans1[196]=12,ans2[196]=31; ans1[197]=17,ans2[197]=27; ans1[198]=12,ans2[198]=31; ans1[199]=12,ans2[199]=31; ans1[200]=12,ans2[200]=31; } /* int num[4]={0,1}; int dp[205]; void biao() { for(int n=4;n<=200;n++) { int b,c; int cnt=inf; for(num[2]=2;num[2]<n;num[2]++) { for(num[3]=num[2]+1;num[3]<=n;num[3]++) { memset(dp,127/3,sizeof dp); dp[0]=0; for(int i=1;i<=3;i++) { for(int j=num[i];j<=n;j++) { dp[j]=min(dp[j-num[i]]+1,dp[j]); } } for(int i=1;i<=n;i++) dp[i]+=dp[i-1]; if(dp[n]<cnt) { b=num[2],c=num[3]; cnt=dp[n]; } } } printf("ans1[%d]=%d,ans2[%d]=%d; ",n,b,n,c); } }*/ int main() { #ifdef local freopen("in","r",stdin); // freopen("out","w",stdout); int _time=clock(); #endif // biao(); init(); int T; cin>>T; while(T--) { int n; cin>>n; printf("%d %d %d ",1,ans1[n],ans2[n]); } #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
B - 柱爷大战滑稽王
求LCS，但是数据n是1e6,特殊的是Ai每个数都不同，我们可以把LCS转LIS，记录Ai在Bi的位置作为一个序列，然后求出这个序列的LIS就是LCS了，这个网上有挺多的
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const LL mod=1000000007; map<int,int>mp; int x[1000005]; int d[1000005]; int lis(int n) { if(!n)return 0; int ans=0; d[0]=x[0]; for(int i=1;i<n;i++){ if(x[i]>d[ans])d[++ans]=x[i]; else{ int pos=lower_bound(d,d+ans+1,x[i])-d; d[pos]=x[i]; } } return ans+1; } int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif int n,m,c; int a; mp.clear(); cin>>n>>m; for(int i=1;i<=n;i++){ sd(a); mp[a]=i; } n=0; for(int i=0;i<m;i++){ sd(a); c=mp[a]; if(c){ x[n++]=c; } } cout<<lis(n)+1<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
N - 柱爷抢银行II
一个环，在环中连续取至多k个数，使得取的数和最大
记sum[i]为前i项和，dp[i]为以i结尾时，dp[i]-i这段范围取得和最大，所以dp[i]=x(i-k<x<i,且max(sum[i]-sum[x])).
单调队列维护sum[i]递减就行
代码写的很渣。。感觉这题有点奇怪题目说了如果想等的话就选区间最小的
3 2
0 0 3
。这种数据，我开始的代码是显示3 3 3一直wa，改了单调队列一点之后变成3 2 3然后居然AC了。
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const LL mod=1000000007; LL sum[2000005]; LL dp[2000005]; LL x[1000005]; int q[2000005]; int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif LL c; int l,r; int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>x[i]; sum[i]=sum[i-1]+x[i]; } for(int i=n+1;i<=2*n;i++){ sum[i]=sum[i-1]+x[i-n]; } q[1]=0; int head=1,tail=1; for(int i=1;i<=2*n;i++) { while(head<=tail&&i-q[head]>k)head++; dp[i]=q[head]; while(sum[i]<sum[q[tail]]&&tail>=head)tail--; q[++tail]=i; } int t=1; for(int i=1;i<=2*n;i++) { if(sum[i]-sum[dp[i]]>sum[t]-sum[dp[t]]) { t=i; } else if(sum[i]-sum[dp[i]]==sum[t]-sum[dp[t]]&&(i-dp[i]<t-dp[t]||(dp[t]+1)-((dp[t]+1)>n?n:0)>(dp[i]+1)-((dp[i]+1)>n?n:0))) { t=i; } } c=sum[t]-sum[dp[t]]; r=t-(t>n?n:0); l=(dp[t]+1)-((dp[t]+1)>n?n:0); cout<<c; printf(" %d %d ",l,r); #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
L - 柱爷的矩阵
假如要选i,j,如果b[i]>b[j],那我们肯定先选b[i],所以先按b[i]降序排序
dp[i][j]表示选取第i列第j行时的最大值,
dp[i][j]=max(dp[i-1][k])(k<j)+max(a[j]-b[j]*(i-1),0);
dp[i-1][k]这个东西我们可以用多个二维数组来维护pre[i][j]=max(dp[i][j-1],dp[i][j]);
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const LL mod=1000000007; struct node { int a,b; }mp[1005]; bool cmp(node a,node b) { return a.b>b.b; } int dp[1005][1005]; int p[1005][1005]; int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif int n,m; cin>>n>>m; for(int i=0;i<n;i++) { cin>>mp[i].a; } for(int i=0;i<n;i++) { cin>>mp[i].b; } sort(mp,mp+n,cmp); int ans=0; for(int i=1;i<=m;i++) { for(int j=0;j<n;j++) { dp[i][j]=p[i-1][j-1]+max(mp[j].a-mp[j].b*(i-1),0); p[i][j]=max(p[i][j-1],dp[i][j]); ans=max(p[i][j],ans); } } cout<<ans<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
I - 柱爷与子序列
这题和FZU有一题很像。树状数组好题。
dp[i]=sum(dp[A[i]]-k],dp[A[i]]+k])+1.
这样答案算是算不考虑m>=2的。所以我们最后需要减去n;
每次查询(A[i]-k，A[i]+k)区间和=sum，然后再在add(A[i],sum+1),最后read(最远点)-n.数据太大，需要离散化一下。
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) #define maxn 1000005 const int inf=0x3f3f3f3f; const int mod=1000000009; int nn; int tree[100005]; int a[100005],b[100005]; void add(int d,int x) { while(d<=nn) { tree[d]=(tree[d]+x)%mod; d+=(d&-d); } } int read(int x) { int sum=0; while(x) { sum=(sum+tree[x])%mod; x-=(x&-x); } return sum; } int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif int n,k; cin>>n>>k; for(int i=0;i<n;i++) { sd(a[i]); b[i]=a[i]; } sort(a,a+n); nn=unique(a,a+n)-a; int z,l,r; for(int i=0;i<n;i++) { z=lower_bound(a,a+nn,b[i])-a+1; l=lower_bound(a,a+nn,b[i]-k)-a+1; r=upper_bound(a,a+nn,b[i]+k)-a; int sum=(read(r)-read(l-1)+mod)%mod; add(z,sum+1); } cout<<(read(nn)-n+mod)%mod<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
G - 柱爷与三叉戟不得不说的故事
15种元素，状压DP搞一下1<<15种状态，
dp[i]=min(dp[i],dp[j]+dp[i^j]);
开始全部初始化为最大值，然后根据条件保留各个状态的最小值最后答案是dp[1<<15-1];
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) const int inf=0x3f3f3f3f; const int mod=1000000009; const int maxn=(1<<15)+5; int dp[maxn]; int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif memset(dp,127/3,sizeof dp); int d,a; for(int i=0;i<15;i++) cin>>d,dp[1<<i]=d; int n; cin>>n; for(int i=0;i<n;i++) { int m; sd(m); int sta=0; for(int j=0;j<m;j++) { sd(a); sta+=(1<<(a-1)); } cin>>d; dp[sta]=min(dp[sta],d); } int last=(1<<15)-1; for(int i=1;i<=last;i++) { for(int j=i;j;j=(j-1)&i) { dp[i]=min(dp[i],dp[j]+dp[j^i]); } } cout<<dp[last]<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
A - 柱爷的恋爱
区间dp
dp[i][j]表示[i,j)的所有合法方案
dp[i][i]=1;
然后我们记忆化递归
dfs(i,j)
假设我们不删i的话我们就需要找出和i对应的括号来算
res+=dfs(i+1,a)*dfs(a+1,j);算出每一个a.
如果删去i就是直接res+=dfs(i+1,j);
最后减1，因为答案不允许删掉所有东西。。
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) const int inf=0x3f3f3f3f; const int mod=1000000007; const int maxn=300+5; LL dp[maxn][maxn]; char s[maxn]; LL dfs(int l,int r) { int ans=0; if(dp[l][r]!=-1)return dp[l][r]; if(l==r) ans=1; else { dp[l][r]=0; char fi=' '; if(s[l]=='(')fi=')'; if(s[l]=='[')fi=']'; if(fi!=' ') { for(int i=l+1; i<r; i++) { if(s[i]==fi) { ans=(ans+dfs(l+1,i)*dfs(i+1,r))%mod; } } } ans=(ans+dfs(l+1,r))%mod; } dp[l][r]=ans; return ans; } int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif for(int i=0; i<maxn; i++)for(int j=0; j<maxn; j++)dp[i][j]=-1; int n; cin>>n; cin>>s; cout<<(dfs(0,n)+mod-1)%mod<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
M - 柱爷的宝藏
普通转移就是，记dp[i]为以i结尾的最大值
dp[i]=max(dp[j]+(sum[i]-sum[j])^2+m);
n^2肯定TLE。然后就学到一个奇妙的斜率优化。。(http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html)
#include <iostream> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <cstdlib> #include <cmath> #include <map> #include <stack> #include <vector> #include <set> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef double db; #define X first #define Y second #define mp(a,b) make_pair(a,b) #define pb push_back #define sd(x) scanf("%d",&(x)) #define Pi acos(-1.0) #define sf(x) scanf("%lf",&(x))//GL&HF #define ss(x) scanf("%s",(x)) const int inf=0x3f3f3f3f; const int mod=1000000007; const int maxn=300+5; LL dp[500005]; LL sum[500005]; LL m; int q[500005]; int n; LL getdp(int i,int j) { return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m; } LL dp_up(int i,int j) { return dp[i]+sum[i]*sum[i]-(dp[j]+sum[j]*sum[j]); } LL dp_down(int i,int j) { return 1LL*2*(sum[i]-sum[j]); } int main() { #ifdef local freopen("in","r",stdin); //freopen("out","w",stdout); int _time=clock(); #endif cin>>n>>m; for(int i=1;i<=n;i++) cin>>sum[i],sum[i]+=sum[i-1]; dp[0]=0; int head=0,tail=0; q[tail++]=0; for(int i=1;i<=n;i++) { while(head+1<tail&&dp_up(q[head+1],q[head])<=sum[i]*dp_down(q[head+1],q[head]))head++; dp[i]=getdp(i,q[head]); while(head+1<tail&&dp_up(i,q[tail-1])*dp_down(q[tail-1],q[tail-2])<=dp_up(q[tail-1],q[tail-2])*dp_down(i,q[tail-1]))tail--; q[tail++]=i; } cout<<dp[n]<<endl; #ifdef local printf("time: %d ",int(clock()-_time)); #endif }
还有几题有点打算弃坑。。