欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  数据库

Topcoder srm 653 div.2 1000

程序员文章站 2022-05-22 08:46:59
...

题意: 给出一个序列，请你找出两个没有交且并为全集的子序列，使得每个子序列相邻两位之间的数字差的绝对之和最

题意:

给出一个序列，请你找出两个没有交且并为全集的子序列，使得每个子序列相邻两位之间的数字差的绝对值之和最小。

思路:

DP....(dp弱渣, 折腾了好久请教了人才会>,<..>

dp[i][j] 表示一人最后一个取的位置是i, 一人最后一个取的位置是j.

分两种情况:

1.i-j>1: dp[i][j] = dp[i-1][j] + abs(pitch[i-2]-pitch[i-1]) 让A一直取数..

2.i-j=1: 1) A只取i, 其他的都给B.

2)A取j, 枚举A上一次取的位置k,B取i, 上一次取k: res = min(res, dp[j][k] + abs(pitch[i-1]-pitch[k-1]))

理解: 两个人会把其中一个位置当做他取的最后一个位置, 那另一个人取的最后一个位置就是最后一个数了. 可以先想比如只有3个人, 这样写是可以把所有的情况涵盖的,相当于问题的子问题.

AC.

    #line 7 "SingingEasy.cpp"
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 

    using namespace std;

    #define PB push_back
    #define MP make_pair

    #define REP(i,n) for(i=0;i=(l);--i)

    typedef vector VI;
    typedef vector VS;
    typedef vector VD;
    typedef long long LL;
    typedef pair PII;


    int dp[2005][2005];

    class SingingEasy
    {
            public:
            int solve(vector  pitch)
            {
                int len = pitch.size();
                if(len  1) {
                            dp[i][j] = dp[i-1][j] + abs(pitch[i-2]-pitch[i-1]);
                        }
                        else {
                            int res = 1e9+5;
                            for(int k = 1; k

相关标签： Topcoder srm 653 div.2 1000 题意

上一篇： javascript - 在node中引用了connect之后，用它自带的中间件总是会报错

下一篇： Mysql中Insert into xxx on duplicate key update问题

推荐阅读