求助插头dp
查看原帖
求助插头dp
245875
Ame__楼主2020/9/5 16:15

RT,样例在跑的时候前两行还正常第三行突然跑到4100了。。。交上去竟然还A了5个点,想知道哪里有问题

#include<bits/stdc++.h>
    
#define LL long long
    
#define _ 0
    
using namespace std;
    
/*Grievous Lady*/
    
template <typename _n_> void mian(_n_ & _x_){
    _x_ = 0;int _m_ = 1;char buf_ = getchar();
    while(buf_ < '0' || buf_ > '9'){if(buf_ == '-')_m_ =- 1;buf_ = getchar();}
    do{_x_ = _x_ * 10 + buf_ - '0';buf_ = getchar();}while(buf_ >= '0' && buf_ <= '9');_x_ *= _m_;
}
    
#define INF 0x3f3f3f3f

#define get_max(x , y) \
{ \
    x = max(x , y); \
}

#define int long long

inline int oqs(int x , int y){
    return x << (y << 1);
}

const int kato = 100 + 10;

int n , m , val[kato][kato];

unordered_map<int , LL> dp[2];

inline LL DP(){
    int tmp = (1 << ((m + 1) << 1)) - 1; 
    LL numnow = 0 , numnxt = 1 , ans = -INF;
    dp[numnow][0] = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            dp[numnxt].clear();
            for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
                // cout << "QAQ" << '\n';
                int S = k -> first; LL last = k -> second;
                LL now = last + val[i][j];
                int L = (S >> ((j - 1) << 1)) & 3 , R = (S >> (j << 1)) & 3;
                if(!L && !R){
                    if(j < m) get_max(dp[numnxt][S ^ oqs(1 , j - 1)^ oqs(2 , j)] , now);
                    get_max(dp[numnxt][S] , last);
                }
                if(L && !R){
                    if(i < n) get_max(dp[numnxt][S] , now);
                    if(j < m) get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(L , j)] , now);
                }
                if(!L && R){
                    if(i < n) get_max(dp[numnxt][S ^ oqs(R , j) ^ oqs(R , j - 1)] , now);
                    if(j < m) get_max(dp[numnxt][S] , now);
                }
                if(L == R){
                    if(L == 1 && R == 1){
                        int nowar = 0;
                        for(int p = j ; ; p ++){
                            int dou = (S >> (p << 1)) & 3;
                            if(dou == 1) nowar ++;
                            if(dou == 2) nowar --;
                            if(nowar == 0){
                                get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(2 , p) ^ oqs(1 , p)] , now);
                                break;
                            }
                        }
                    }
                    if(L == 2 && R == 2){
                        int nowar = 0;
                        for(int p = j - 1; ; p --){
                            int dou = (S >> (p << 1)) & 3;
                            if(dou == 2) nowar ++;
                            if(dou == 1) nowar --;
                            if(nowar == 0){
                                get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j) ^ oqs(1 , p) ^ oqs(2 , p)] , now);
                                break;
                            }
                        }
                    }
                }
                if(L == 2 && R == 1){
                    get_max(dp[numnxt][S ^ oqs(L , j - 1) ^ oqs(R , j)] , now);
                }
                if(L == 1 && R == 2 && (S ^ oqs(L , j - 1) ^ oqs(R , j)) == 0){ ans = max(ans , now); }
            }
            swap(numnow , numnxt);
        }
        dp[numnxt].clear();
        for(auto k = dp[numnow].begin(); k != dp[numnow].end(); k ++){
            dp[numnxt][(k -> first << 2) & tmp] += k -> second;
        }
        swap(numnxt , numnow);
        // cout << ans << '\n';
    }
    return ans;
}

inline int Ame_(){
    mian(n) , mian(m);
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            mian(val[i][j]);
        }
    }
    printf("%lld\n" , DP());
    return ~~(0^_^0);
}
    
int Ame__ = Ame_();
    
signed main(){;}

/*
4 4
100 300 -400 400
-100 1000 1000 1000
-100 -100 -100 -100
-100 -100 -100 1000
*/
2020/9/5 16:15
加载中...