HDU - 6981 Rise in Price

传送门：HDU - 6981

思路分析

设$dp_{i,j,k}$表示走到$(i,j)$，拿了$k$个钻石时最高单价是多少。

对于同一个位置$(i,j)$来说，如果$dp_{i,j,k_1} \geq dp_{i,j,k_2} , k_1\geq k_2$ 那么显然$k_2$不论什么情况，最后最优解都不会是它，$k_1$都比它好，所以$k_2$这个状态可以剔除掉。

由于数据随机，有效的$k$值大约几千，能过

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int N = 111;

int a[N][N],b[N][N];
V<pii> dp[N][N];

void merge(V<pii>&ans,const V<pii>&x,const V<pii>&y){
    int n = sz(x);
    int m = sz(y);
    int i=0,j=0;
    int ma = 0;
    while(i<n && j<m) {
        if(x[i].fi>y[j].fi){
            if(x[i].se>ma){
                ma = x[i].se;
                ans.pb(x[i]);
            }
            i++;
        }else{
            if(y[j].se>ma){
                ma = y[j].se;
                ans.pb(y[j]);
            }
            j++;
        }
    }
    while(i<n) {
        if(x[i].se>ma){
            ma = x[i].se;
            ans.pb(x[i]);
        }
        i++;
    }
    while(j<m){
        if(y[j].se>ma){
            ma = y[j].se;
            ans.pb(y[j]);
        }
        j++;
    }
    return ;
}

signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j].clear();
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j];
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>b[i][j];
        dp[1][1].pb(mp(a[1][1],b[1][1]));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i+j==2) continue;
                if(i == 1) dp[i][j] = dp[i][j-1];
                else if(j==1) dp[i][j] = dp[i-1][j];
                else merge(dp[i][j],dp[i-1][j],dp[i][j-1]);
                each(x,dp[i][j]) x.fi+=a[i][j],x.se+=b[i][j];
            }
        }
        ll ans = 0;
        each(x,dp[n][n]) ans = max(ans,(ll)x.fi*x.se);
        cout<<ans<<endl;

    }



/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}