序列最大收益

ysDP

算法思路

    思考时最难想到的就是状态如何定义.可以想到用二维表示状态dp[i][j],i限制选择的序列,j限制删除的个数.
但一直没想到如何定义能计算删或删的收益.(不删那么哪一个序列与a[i]相邻).状态的定义类似最长上升
子序列的定义.
    dp
    状态表示
        dp[i][j]
        集合:只考虑前i个序列,删除j个序列且第i个数保留的所有方案的集合
        属性:收益的最大值Max
    状态计算    
        最长上升子序列的dp[i]表示第i个数保留,状态的划分依据前一个数是哪位来划分.这里相同,
    以前一个数哪位删除,即中间的各位都被删除了,前一个数u在[1,i-1]之间.
        确定部分:保留u和i,那么确定有收益w(a[u],a[i]);可变部分:u-i中间删除了c = u - i - 1个,
    那么要在1-u之间删除 j - c 个,为符合状态属性最大,可变部分也要取最大,即dp[u][j-c].

    问题还有一个性质:两端的序列可以在最优解中.假设最优解中不存在两端序列,因为收益w>=0,加入
    两端符合条件且收益不会减少,所以可以加入.那么最后解在dp[m][i]中找最大即可.

时间复杂度

状态个数 * 状态转移 = O($n^2$)

C++ 代码

#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 210;

int n, k, m;
int a[N];
int w[N][N];
int dp[N][N];

int main()
{
    cin >> n >> k >> m;
    for( int i = 1; i <= m; i++ )   cin >> a[i];
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j <= n; j++ )
            cin >> w[i][j];

    memset(dp,-0x3f,sizeof dp);//初始状态
    dp[1][0] = 0; //1可以在最优解中 只有一个元素无收益
    for( int i = 2; i <= m; i++ )
    {
        for( int j = 0; j <= k; j++ )
        {
            for( int u = 1; u < i; u++ )
            {
                int c = i - u - 1;//u-i之间要删除个数
                if( j >= c )
                {//总删除个数要大于u-i之间的个数
                    dp[i][j] = max( dp[i][j], dp[u][j-c] + w[a[u]][a[i]]);
                }
            }
        }
    }

    int res = 0;
    for( int i = 0; i <= k; i++ )
        res = max( res, dp[m][i] );
    cout << res << endl;

    return 0;
}