《算法竞赛进阶指南》0x51线性DP POJ3666分级

2021-04-08 16:25

阅读：600

标签：target 重要 href 数学 names 个数 code 证明相减

题目链接：http://poj.org/problem?id=3666、

题目给出一个序列a，要求给出一个序列b使得两个数列每一项相减的绝对值之和最小，这里有一个重要的性质：存在一个满足条件的b，其中的数在a中都出现，可以通过数学归纳法去证明。

然后就是dp的转移，前i个数设定好，并且第i个数是第j大的a中的数，这时的转移方程是dp[i][j]=min{dp[i-1][k]}+abs(a[i]-a‘[j])，其中k属于[1,j]。

通过前缀最大值的思想容易优化成O(n^2)

代码：

#include
#include
#include
using namespace std;
const int maxn = 2020;
int a[maxn],b[maxn];
int f[maxn][maxn];
const int inf=0x7fffffff;
int n;
int dp(){
    for(int i=1;ia[i];
    sort(b+1,b+n+1);
    for(int i=1;i){
        int minv=inf;
        for(int j=1;j){
            minv=min(minv,f[i-1][j]);
            f[i][j]=minv+abs(a[i]-b[j]);
        }
    }
    int res=inf;
    for(int i=1;imin(res,f[n][i]);
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i>a[i];
    int res=dp();
    reverse(a+1,a+n+1);
    res=min(res,dp());
    coutendl;
}

《算法竞赛进阶指南》0x51线性DP POJ3666分级

标签：target 重要 href 数学 names 个数 code 证明相减

原文地址：https://www.cnblogs.com/randy-lo/p/13377919.html

上一篇：Web Api HelpPage

下一篇：Java基础之嵌套循环

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：《算法竞赛进阶指南》0x51线性DP POJ3666分级
文章链接：http://soscw.com/index.php/essay/72933.html

亲，登录后才可以留言！

《算法竞赛进阶指南》0x51线性DP POJ3666分级

评论

热门文章

推荐文章

最新文章

置顶文章