中南1699 Live Programming

柔情只为你懂 2022-07-28 00:15 32阅读 0赞

这道题是dp的斜率优化 然而并不会优化 先把未优化的码一下，以后学会了优化再来改

题目链接：[http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1699][http_acm.csu.edu.cn_OnlineJudge_problem.php_id_1699]

题目大意：  
给你n首歌，每首歌都有自己的时间t，分值p，特征值f，每唱一首歌都会得到p分，但会减去本首歌与前一首歌特征值的平方差（第一首不用减），给出总时间T，问最多能得到多少分。

解题思路：  
首先用sort按特征值排序（正序倒序皆可），因为这样特征值的平方差和能最小，最后选出的歌的顺序肯定是按这样的。这样就和0，1背包差不多了。

dp\[i\]\[j\] i为唱的最后一首歌， j为总时间  
初始化

if(j>=a[i].t) dp[i][j]=a[i].p;
     else dp[i][j]=-inf;

递推：

for(int i=1; i<n; i++)
        for(int j=a[i].t+1; j<=t; j++)
             for(int k=0; k<i; k++)
                dp[i][j]=
      max(dp[i][j],dp[k][j-a[i].t]+a[i].p-cal(a[i].f,a[k].f));

但是有两点是特殊的，第一点是为了确定唱的最后一首歌的是哪一首，所以当给出的j无法满足最后一首歌的时间时，就什么也不干。第二点是当满足最后一首歌的时间时，要从0到i-1遍历一遍来查找最大值，所以最终的复杂度是tn^2，要用到斜率优化成t\*n。

这个博客讲斜率优化不错  
[http://blog.csdn.net/iaccepted/article/details/6699691][http_blog.csdn.net_iaccepted_article_details_6699691]

之前有一个这样的想法，能否用dp\[i\]\[j\]表示前i首歌在j时间内分数的最大值，然后新开一个dp1\[\]\[\]数组来表示当前最大值的最后一首歌是哪一首，后来递推了一下，发现是错的  
比如说这样一组数据

3 14  
6 105 1  
7 102 9  
7 101 10

按照我的想法dp\[2\]\[7\]=105 ，然后标记最后一首唱的歌为第一首，这样算第三首的时候就会得到，dp\[3\]\[14\]=105+101-81=120，但实际上dp\[2\]\[7\]=102,dp\[3\]\[14\]=102+101-1=202 这才是正解，其实就是某一首歌可能确实在前几首歌中最优，但是因为要减去特征值的平方差，所以结果就不确定了，必须要递推一遍。

下面是t\*n^2的代码

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    typedef long long LL;
    long long int dp[4000][4000];
    int cal(int a,int b)
    {
        return (a-b)*(a-b);
    }
    
    struct song
    {
        int t;
        int p;
        int f;
    };
    bool cmp(song a,song b)
    {
        return a.f<b.f;
    }
    int main()
    {
        int n,t;
        RII(n,t);
        song a[4005];
        for(int i=0; i<n; i++)
        {
            RIII(a[i].t,a[i].p,a[i].f);
        }
        sort(a,a+n,cmp);
    
        for(int i=0; i<=n; i++)
        {
            for(int j=0; j<=t; j++)
            {
                if(j>=a[i].t) dp[i][j]=a[i].p;
                else dp[i][j]=-inf;
            }
        }
    
        for(int i=1; i<n; i++)
            for(int j=a[i].t+1; j<=t; j++)
            {
                for(int k=0; k<i; k++)
                {
                    dp[i][j]=max(dp[i][j],dp[k][j-a[i].t]+a[i].p-cal(a[i].f,a[k].f));
                }
            }
    
        long long int ans=0;
        for(int i=0; i<n; i++)
        {
            ans=max(ans,dp[i][t]);
        }
        cout<<ans<<endl;
        return  0;
    }

[http_acm.csu.edu.cn_OnlineJudge_problem.php_id_1699]: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1699
[http_blog.csdn.net_iaccepted_article_details_6699691]: http://blog.csdn.net/iaccepted/article/details/6699691