ToB企服应用市场:ToB评测及商务社交产业平台

标题: AcWing 1027. 方格取数 [打印本页]

---

作者: 科技颠覆者    时间: 2022-8-9 14:41
标题: AcWing 1027. 方格取数

1. 题意等价于：选择两条从A到B的路径，路径上的点对答案至多贡献一次，求最大值
2. 很容易想到先计算第一条路径，再计算第二条路径(f[i1][j1][i2][j2])，判断重合的点，但这样没有利用重合点的必要性，有时间和空间上的冗余
3. 进一步想到，每对重合点的横纵坐标之和必定相等
4. 也就是说只有当i1 + j1 == i2 + j2时，两条路径上的点才有可能重合，这就是我们要特殊处理的情况
5. 不妨设k = i1+j1，这样枚举的状态就从四维降到了三维，只需计算状态f[k][i1][i2]即可（两点重合等价于i1 == i2）

复制代码

[code]#includeusing namespace std;#define int long long#define fr first#define se secondtypedef pair PII;typedef unsigned long long ULL;const int INF = 0X3f3f3f3f, N = 20, MOD = 1e9 + 10;int w[N][N];int f[2*N][N][N];void work() {    int n;    cin>>n;        int a,b,c;    while(cin>>a>>b>>c,a||b||c) w[a]=c;    for(int k=2;k

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4