2k21電腦無腦包夾，hdu1421 搬寢室 DP

2023-12-07 阅读 27 评论 0

摘要：轉載： /*證明：從4個數中 a b c d??依次遞增；選取相鄰的兩個數一定是最小得 2k21電腦無腦包夾？及:(a-b)^2+(c-d)^2<(a-c)^2+(b-d)^2&&(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2; //先排序，假設從n-1個中選取k對是最少得&#

轉載：

/*證明：從4個數中 a b c d??依次遞增；

選取相鄰的兩個數一定是最小得

2k21電腦無腦包夾？及:(a-b)^2+(c-d)^2<(a-c)^2+(b-d)^2&&(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2;

//先排序，假設從n-1個中選取k對是最少得，那么從n個中選取k對，可以這樣分析對n-1個數再在末尾增加一個數，那么這個數可能被選中成為k對中其中一對，可能不被選中，如果不被選中，那么從n個中選取k對就相當于從n-1個中選取k對，如果被選中，之前證明了選中的數必須是連續的兩個才能事最小，那就相當于從n-2個數中選取k-1對加最后兩個數成為，這樣，狀態轉移方程就為dp[i][j]=min(dp[(i-1)][j],dp[(i-2)][j-1]+(a[i-1]-a[i])*(a[i-1]-a[i]));

我的AC代碼：

搬寢室算搬家嗎、?

 1 #include<cstdlib>
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 #define MAX 2010
 9 int dp[MAX][MAX];
10 int f[MAX];
11 int n,k;
12 int main()
13 {
14        while(scanf("%d%d",&n,&k)!=EOF)
15        {
16                int i,j;
17                for( i=1;i<=n;i++)
18                        scanf("%d",&f[i]);
19                sort(f+1,f+n+1);
20                memset(dp,0,sizeof(dp));
21                for( i=2;i<=n;i++)
22                        for( j=1;j<=k&&j*2<=i;j++)
23                                if(i==j*2) dp[i][j]=dp[i-2][j-1]+(f[i]-f[i-1])*(f[i]-f[i-1]);
24                                else
25                                dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(f[i]-f[i-1])*(f[i]-f[i-1]));
26                cout<<dp[n][k]<<endl;
27        }
28        return 0;
29 }