[关闭]
@ysner 2018-08-05T21:16:52.000000Z 字数 1436 阅读 2387

[luogu_U15116]珈百璃堕落的开始

DP


题面

给定个二元组,问有多少种方案,使得选出其中几个后,

解析

在打比赛时又被傻逼DP切了
考虑到我们关注的是,我们可以维护一维状态以代替两维状态。
于是设表示在第个数中,的方案数。
可以为负,记得开大空间。
转移显然。

但有几个要注意的地方。
如果暴力枚举,复杂度可以达到,数据没有保证这样能过。
注意到中有很多转移是从不合法状态转移到不合法状态。
既然开始状态为(防止状态出现负数),范围很小。我们可以维护一下当前被转移到了的区间范围,这样能大大降低时间复杂度。

还有,值的边界条件要求必须能把未转移到的状态和转移到的状态区分开来
所以初始所有值要设为除外。

  1. // luogu-judger-enable-o2
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<cmath>
  7. #include<algorithm>
  8. #include<vector>
  9. #define re register
  10. #define il inline
  11. #define ll long long
  12. #define max(a,b) ((a)>(b)?(a):(b))
  13. #define min(a,b) ((a)<(b)?(a):(b))
  14. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  15. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  16. using namespace std;
  17. const int N=2e6+100,M=1e6;
  18. int n,m,s[N],c[N],len,dp[2][N];
  19. char a[N];
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. int main()
  30. {
  31. n=gi();
  32. fp(i,1,n)
  33. {
  34. scanf("%s",a+1);len=strlen(a+1);
  35. fp(j,1,len) if(a[j]=='s') s[i]++;else if(a[j]=='c') c[i]++;
  36. }
  37. re int now=1,nxt=0,lasx=M,lasm=M,mn=M,mx=M;
  38. memset(dp,-63,sizeof(dp));dp[1][M]=0;
  39. fp(i,1,n)
  40. {
  41. swap(now,nxt);
  42. fp(j,lasm,lasx)
  43. {
  44. dp[now][j+s[i]-c[i]]=max(dp[now][j+s[i]-c[i]],dp[nxt][j]+s[i]);
  45. dp[now][j]=max(dp[now][j],dp[nxt][j]);
  46. dp[nxt][j]=0;
  47. mx=max(mx,j+s[i]-c[i]),mn=min(mn,j+s[i]-c[i]);
  48. }
  49. lasx=mx;lasm=mn;
  50. }
  51. printf("%d\n",dp[now][M]);
  52. return 0;
  53. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注