ARC074 E RGB sequence(800)

高次元DPをやる

dp[300][300][300]を作るのは雰囲気でそうなるが、工夫しないとMLEをするので頑張る

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<queue>
5. #define mod 1000000007;
6. #define lol(i,n) for(int i=0;i<n;i++)
7. typedef long long ll;
8. using namespace std;
9.  
10. ll dp[303][303][303];
11. int rest[310][4];
12.  
13. bool Cando(int a,int b,int c){
14. int e1=max(a,max(b,c));
15. int e3=min(a,min(b,c));
16. int e2=a+b+c-e1-e3;
17. if(rest[e1][1]<=e2&&e2<rest[e1][0]&&rest[e1][3]<=e3&&e3<rest[e1][2]){
18. return true;
19. }
20. return false;
21. }
22.  
23. int main(){
24. int n,m;
25. cin>>n>>m;
26. lol(i,n+1){
27. rest[i][0]=mod;//left1
28. rest[i][2]=mod;//left2
29. rest[i][1]=-1;//right2
30. rest[i][3]=-1;//right3
31. }
32. lol(i,m){
33. int a,b,c;
34. cin>>a>>b>>c;
35. if(c==1)rest[b][0]=min(rest[b][0],a);
36. if(c==3)rest[b][3]=max(rest[b][3],a);
37. if(c==2){
38. rest[b][1]=max(rest[b][1],a);
39. rest[b][2]=min(rest[b][2],a);
40. }
41. }
42. lol(i,n+1)lol(j,n+1)lol(k,n+1)dp[i][j][k]=0;
43. dp[0][0][0]=1;
45. for(int len=0;len<=n;len++){
46. for(int i=0;i<max(1,len);i++){
47. for(int j=0;j<max(1,i);j++){
49. int R=len,G=i,B=j;
50. if(Cando(R,G,B)==false)continue;
52. int a=len+1,b=G,c=B;
53. int e1=max(a,max(b,c));
54. int e3=min(a,min(b,c));
55. int e2=a+b+c-e1-e3;
56. dp[e1][e2][e3]+=dp[R][G][B];
57. dp[e1][e2][e3]%=mod;
59. a=R,b=len+1,c=B;
60. e1=max(a,max(b,c));
61. e3=min(a,min(b,c));
62. e2=a+b+c-e1-e3;
63. dp[e1][e2][e3]+=dp[R][G][B];
64. dp[e1][e2][e3]%=mod;
66. a=R,b=G,c=len+1;
67. e1=max(a,max(b,c));
68. e3=min(a,min(b,c));
69. e2=a+b+c-e1-e3;
70. dp[e1][e2][e3]+=dp[R][G][B];
71. dp[e1][e2][e3]%=mod;
72. }
73. }
74. }
76. ll ans=0;
77. for(int i=0;i<n;i++){
78. for(int j=0;j<max(i,1);j++){
79. if(Cando(n,i,j)){
80. ans+=dp[n][i][j];
81. ans%=mod;
82. }
83. }
84. }
85. ans%=mod;
86. cout<<ans<<endl;
87. return 0;
88. }

無理にコードを短くしないようにする

 (愚直に分かりやすく書く)