AcWing 1027. 方格取数
https://img2022.cnblogs.com/blog/2792543/202206/2792543-20220624013610941-2101664356.png题意等价于:选择两条从A到B的路径,路径上的点对答案至多贡献一次,求最大值
很容易想到先计算第一条路径,再计算第二条路径(f),判断重合的点,但这样没有利用重合点的必要性,有时间和空间上的冗余
进一步想到,每对重合点的横纵坐标之和必定相等
也就是说只有当i1 + j1 == i2 + j2时,两条路径上的点才有可能重合,这就是我们要特殊处理的情况
不妨设k = i1+j1,这样枚举的状态就从四维降到了三维,只需计算状态f即可(两点重合等价于i1 == i2)https://img2022.cnblogs.com/blog/2792543/202206/2792543-20220624133332800-1417142846.png
#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;int f;void work() { int n; cin>>n; int a,b,c; while(cin>>a>>b>>c,a||b||c) w=c; for(int k=2;k
页:
[1]