誰能幫我解決這個問題？
給定 n 個整數和一個數字 k (k<=n/2)。找出陣列中 k 對的絕對差的最小和。
示例 1：
輸入：
5 2
2 5 3 3 6
輸出：
1
解釋：|3 - 3| |6 - 5| = 1
示例 2：
輸入：
6 3
868 504 178 490 361 603
輸出：
462
解釋： |868 - 603| |504 - 490| |178 - 361| = 462
我曾嘗試過蠻力，但無法通過其他大量測驗用例。我認為這可以通過動態編程來解決，但不知道該怎么做。
這是我的代碼：
#include<bits/stdc .h>
using namespace std;
struct PAIR
{
long long a,b,c;
};
bool compare(PAIR fi,PAIR se)
{
return fi.c<se.c;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n,k;
cin>>n>>k;
long long a[n 1];
for(int i=1;i<=n;i )
{
cin>>a[i];
}
long long f[n 1][n 1];
for(int i=1;i<=n;i )
{
for(int j=i;j<=n;j )
{
f[i][j]=abs(a[i]-a[j]);
}
}
vector<PAIR>t;
long long index=0;
for(int i=1;i<=n;i )
{
for(int j=i;j<=n;j )
{
if(i!=j)
{
t.push_back(PAIR());
t[index].a=i;
t[index].b=j;
t[index].c=f[i][j];
index ;
}
}
}
sort(t.begin(),t.end(),compare);
long long res=1e9;
for(int i=0;i<t.size();i )
{
long long temp=t[i].c,l=1;
map<long long,long long>cnt;
cnt[t[i].b] ;
cnt[t[i].a] ;
for(int j=0;j<t.size();j )
{
if(l==k) break;
if(cnt[t[j].a]==0&&cnt[t[j].b]==0)
{
temp =t[j].c;
cnt[t[j].a] ;
cnt[t[j].b] ;
l ;
}
}
res=min(res,temp);
}
cout<<res;
return 0;
}
uj5u.com熱心網友回復：
假設O(N * K)解決方案會通過，那么我們可以使用dynamic programming.
讓dp[i][j]成為使用第一個排序i數字的最小成本，使用j對。我們可以寫：
dp[0][j] = INT_MAX; // for each j between 0 and K.
dp[i][j] = std::min(dp[i - 1][j], a[i] - a[i - 1] dp[i - 2][j - 1]); // for each j between 0 and i / 2
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505889.html