AcWing 1012. 友好城市 dp_综合

AcWing 1012. 友好城市

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式
第1行，一个整数N，表示城市数。

第2行到第n+1行，每行两个整数，中间用1个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出格式
仅一行，输出一个整数，表示政府所能批准的最多申请数。

数据范围
1≤N≤5000,
0≤xi≤10000
输入样例：

输出样例：

这道题是一个dp题，我们采用闫氏分析法。

状态表示：
$d p [k, i 1, i 2]$ 表示横纵坐标之和为k的情况下，走到坐标为i1,i2的捡东西的最大价值。

求的是MAX
状态计算：

我们这个点只能向右，或者向下。

在这里插入图片描述

               int &v=f[k][i1][i2];v=max(f[k-1][i1][i2]+t,v);v=max(f[k-1][i1-1][i2]+t,v);v=max(f[k-1][i1][i2-1]+t,v);v=max(f[k-1][i1-1][i2-1]+t,v);

最后我们开始写代码
需要注意的是，如果出现重复的情况下，我们是不执行状态计算的，因为已经相交了，然后我们只计算不相交的，以及出发点，终点。

代码如下：

#include<iostream>
#include<algorithm>using namespace std;const int N=55;int f[2*N][N][N],g[N][N];int main(void)
{
    int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>g[i][j];for(int k=2;k<=n+m;k++)for(int i1=max(1,k-m);i1<=min(n,k-1);i1++)for(int i2=max(1,k-m);i2<=min(n,k-1);i2++){
    int t=g[i1][k-i1];if(i1!=i2||k==n+m){
    t+=g[i2][k-i2];int &v=f[k][i1][i2];v=max(f[k-1][i1][i2]+t,v);v=max(f[k-1][i1-1][i2]+t,v);v=max(f[k-1][i1][i2-1]+t,v);v=max(f[k-1][i1-1][i2-1]+t,v);}}cout<<f[n+m][n][n];
}