[数据结构与算法]dp-[NOIP2000]方格取数

[NOIP2000]方格取数

n^4

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

const int maxn = 1e2 + 10;
const int N = 6e6 + 100;

int dp[maxn][maxn][maxn][maxn];
int a[maxn][maxn];
int v[maxn];

void solve() {
    int n;
    cin >> n;
    int x, y, w;
    while ((cin >> x >> y >> w)&&!(x==0&&y==0&&w==0))a[x][y] = w;
    dp[1][1][1][1] = a[1][1];
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    for (int k = 1; k <= n; k++)
    for (int g = 1; g <= n; g++) {
//        if (i + j != k + g) continue;
        int ans = a[i][j] + a[k][g];
        if (i == k && j == g) ans /=2;
        dp[i][j][k][g] = max(dp[i][j][k][g], dp[i - 1][j][k - 1][g] + ans);
        dp[i][j][k][g] = max(dp[i][j][k][g], dp[i][j - 1][k - 1][g] + ans);
        dp[i][j][k][g] = max(dp[i][j][k][g], dp[i - 1][j][k][g - 1] + ans);
        dp[i][j][k][g] = max(dp[i][j][k][g], dp[i][j - 1][k][g - 1] + ans);
//        cout<<dp[i][j][k][g]<<endl;
    }
    cout << dp[n][n][n][n];
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();//cout<<"\n";
    }
    return 0;
}

//12341
//14321
//

n^3

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

const int maxn = 1e2 + 10;
const int N = 6e6 + 100;

int dp[maxn][maxn][maxn];
int a[maxn][maxn];
int v[maxn];

void solve() {
    int n;
    cin >> n;
    int x, y, w;
    while ((cin >> x >> y >> w)&&!(x==0&&y==0&&w==0))a[x][y] = w;
    dp[2][1][1] = a[1][1];
    for (int i = 2; i <= 2*n; i++)
    for (int k = 1; k <= n; k++)
    for (int g = 1; g <= n; g++) {
        int x1=k,x2=g,y1=i-k,y2=i-g;
        int ans=a[x1][y1]+a[x2][y2];
        if(x1==x2&&y1==y2) ans/=2;

        dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1-1][x2]);
        dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1][x2-1]);
        dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1][x2]);
        dp[i][k][g]= max(dp[i][k][g],ans+dp[i-1][x1-1][x2-1]);
    }
    cout << dp[2*n][n][n];
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();//cout<<"\n";
    }
    return 0;
}

//12341
//14321
//

空间n^2

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

const int maxn = 1e2 + 10;
const int N = 6e6 + 100;

int dp[maxn][maxn];
int a[maxn][maxn];
int v[maxn];

void solve() {
    int n;
    cin >> n;
    int x, y, w;
    while ((cin >> x >> y >> w)&&!(x==0&&y==0&&w==0))a[x][y] = w;
    for (int i = 2; i <= 2*n; i++)
    for (int k=i; k>0; k--)
    for (int g=i; g>0; g--) {
        int x1=k,x2=g,y1=i-k,y2=i-g;
        int ans=a[x1][y1]+a[x2][y2];
        if(x1==x2&&y1==y2) ans/=2;
        dp[k][g]=max(max(dp[k-1][g],dp[k][g-1]),max(dp[k-1][g-1],dp[k][g]))+ans;
//        cout<<dp[k][g]<<endl;
    }
    cout << dp[n][n];
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();//cout<<"\n";
    }
    return 0;
}

//12341
//14321
//