1. 题目

传送门= ̄ω ̄=

2. 题解

设$f(i,j)$表示在前$i$本书中选$j$本书,且必然选择第$i$本书时的最小差异值。
不难得出状态转移方程:$f(i,j)=min\{f(k,j-1)+abs(w[k]-w[i]) | j-1<=k<i\}$

因此记忆化搜索就AC了。
递归边界:
1. $i==1$或者$j==1$时,$f(i,j)=0$
2. $i==j$直接for一遍暴力计算差异值。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
int n,k,f[105][105],ans=INT_MAX;
bool book[105][105];
pii obj[105];
int dfs(int x,int y)
{
    if(book[x][y])return f[x][y];
    book[x][y]=1;
    if(x==1||y==1)return 0;
    if(x==y)
    {
        for(int i=2;i<=x;i++)f[x][y]+=abs(obj[i].second-obj[i-1].second);
        return f[x][y];
    }
    f[x][y]=INT_MAX;
    for(int i=y-1;i<x;i++)
        f[x][y]=min(f[x][y],dfs(i,y-1)+abs(obj[x].second-obj[i].second));
    return f[x][y];
}
int main()
{
    scanf("%d%d",&n,&k),k=n-k;
    for(int i=1;i<=n;i++)scanf("%d%d",&obj[i].first,&obj[i].second);
    sort(obj+1,obj+1+n);
    for(int i=k;i<=n;i++)ans=min(ans,dfs(i,k));
    printf("%d\n",ans);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *