赛克 1530（环形dp）

赛氪OJ-专注于算法竞赛的在线评测系统 (saikr.com)

枚举第一张卡片是由法力值降低还是法力值上升得到的，一共有4种情况，d[i][j][0]表示第i个卡牌选第j个法力值并且上一个卡牌的法力值大于j的所获得的前i个卡牌的最大运气值；d[i][j][1]表示第i个卡牌选第j个法力值并且上一个卡牌的法力值小于j的所获得的前i个卡牌的最大运气值。

  1 #define IO std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  2 #define bug(x) cout<<#x<<" is "<<x<<endl
  3 #include <bits/stdc++.h>
  4 #define iter ::iterator
  5 using namespace  std;
  6 typedef long long ll;
  7 typedef pair<int,int>P;
  8 #define pb push_back
  9 #define mk make_pair
 10 #define se second
 11 #define fi first
 12 // #define rs o*2+1
 13 // #define ls o*2
 14 const int N=1e5+5;
 15 int n;
 16 int a[N][4];
 17 ll d[N][4][2];
 18 int vis[N][4];
 19 int cnt=0;
 20 void init(){
 21     for(int i=1;i<=n;i++){
 22         for(int j=1;j<=3;j++){
 23             d[i][j][0]=0;
 24             d[i][j][1]=0;
 25         }
 26     }
 27 }
 28 int main(){
 29     IO;
 30     cin>>n;
 31         
 32     for(int i=1;i<=n;i++){
 33         for(int j=1;j<=3;j++)cin>>a[i][j];
 34     }
 35     
 36     d[1][2][0]=a[1][2];
 37     for(int i=2;i<=n;i++){
 38         if(i==n){
 39             for(int j=1;j<=3;j++){
 40                 for(int k=1;k<j;k++){
 41                     d[i][j][1]=max(d[i][j][1],d[i-1][k][0]+a[i][j]);
 42                 }
 43             }
 44             continue;
 45         }
 46         for(int j=1;j<=3;j++){
 47             for(int k=j+1;k<=3;k++){
 48                 d[i][j][0]=max(d[i][j][0],d[i-1][k][1]+a[i][j]);
 49             }
 50             for(int k=1;k<j;k++){
 51                 d[i][j][1]=max(d[i][j][1],d[i-1][k][0]+a[i][j]);
 52             }
 53         }
 54     }
 55     ll ans=d[n][3][1];
 56 
 57     init();
 58     d[1][1][0]=a[1][1];
 59     for(int i=2;i<=n;i++){
 60         if(i==n){
 61             for(int j=1;j<=3;j++){
 62                 for(int k=1;k<j;k++){
 63                     d[i][j][1]=max(d[i][j][1],d[i-1][k][0]+a[i][j]);
 64                 }
 65             }
 66             continue;
 67         }
 68         for(int j=1;j<=3;j++){
 69             for(int k=j+1;k<=3;k++){
 70                 d[i][j][0]=max(d[i][j][0],d[i-1][k][1]+a[i][j]);
 71             }
 72             for(int k=1;k<j;k++){
 73                 d[i][j][1]=max(d[i][j][1],d[i-1][k][0]+a[i][j]);
 74             }
 75         }
 76     }
 77     
 78     ans=max(ans,d[n][3][1]);
 79     ans=max(ans,d[n][2][1]);
 80 
 81     init();
 82     d[1][2][1]=a[1][2];
 83     for(int i=2;i<=n;i++){
 84         if(i==n){
 85             for(int j=1;j<=3;j++){
 86                 for(int k=j+1;k<=3;k++){
 87                     d[i][j][0]=max(d[i][j][0],d[i-1][k][1]+a[i][j]);
 88                 }
 89             }
 90             continue;
 91         }
 92         for(int j=1;j<=3;j++){
 93             for(int k=j+1;k<=3;k++){
 94                 d[i][j][0]=max(d[i][j][0],d[i-1][k][1]+a[i][j]);
 95             }
 96             for(int k=1;k<j;k++){
 97                 d[i][j][1]=max(d[i][j][1],d[i-1][k][0]+a[i][j]);
 98             }
 99         }
100     }
101     ans=max(ans,d[n][1][0]);
102 
103     init();
104     d[1][3][1]=a[1][3];
105     for(int i=2;i<=n;i++){
106         if(i==n){
107             for(int j=1;j<=3;j++){
108                 for(int k=j+1;k<=3;k++){
109                     d[i][j][0]=max(d[i][j][0],d[i-1][k][1]+a[i][j]);
110                 }
111             }
112             continue;
113         }
114         for(int j=1;j<=3;j++){
115             for(int k=j+1;k<=3;k++){
116                 d[i][j][0]=max(d[i][j][0],d[i-1][k][1]+a[i][j]);
117             }
118             for(int k=1;k<j;k++){
119                 d[i][j][1]=max(d[i][j][1],d[i-1][k][0]+a[i][j]);
120             }
121         }
122     }
123     ans=max(ans,d[n][1][0]);
124     ans=max(ans,d[n][2][0]);
125 
126     cout<<ans<<endl;
127 }
128 /*
129 6
130 3 10 4
131 5 5 1
132 6 10 7
133 4 5 3
134 9 9 8
135 6 9 2
136 
137 */