学步园

//虽然看着dp的ppt，但是刚开始做还是用了深搜，毫无疑问，TLE<br /> //想着不对路，但是想不到怎么用dp，百度，搜到了转移方程：<br /> //分两种情况<br /> //当i-1>=j*2时<br /> //b[i][j]=min{b[i-1][j], b[i-2][j-1]+(a[i]-a[i-1])^2} .<br /> //当i-1<j*2时<br /> //b[i][j]=b[i-2][j-1]+(a[i]-a[i-1])^2 .<br /> #include <iostream><br /> #include <cstring><br /> #include <cmath><br /> #include <algorithm><br /> using namespace std;<br /> struct node {<br /> int x;<br /> int y;<br /> int tired;<br /> }data[2010];<br /> int a[2010];<br /> bool isVis[2010];<br /> int n, k;<br /> int ans;<br /> int _count;<br /> //第一维表示元素个数i，第二维表示对数j，表示从i个元素中选j对最小的疲累度<br /> int tired[2010][1010];<br /> //bool cmp(const node& A, const node& B) {<br /> // return A.tired < B.tired;<br /> //}<br /> //bool dfs(int cur) {<br /> // if(_count == k) return true;<br /> // for(int i = cur; i < n - 1 && k - _count <= n - 1 - i; i++) {<br /> // if(!isVis[data[i].x] && !isVis[data[i].y]) {<br /> // bool tmpX = isVis[data[i].x];<br /> // bool tmpY = isVis[data[i].y];<br /> // ans += data[i].tired;<br /> // _count++;<br /> // isVis[data[i].x] = isVis[data[i].y] = true;<br /> // if(dfs(i + 1)) return true;<br /> // isVis[data[i].x] = tmpX;<br /> // isVis[data[i].y] = tmpY;<br /> // ans -= data[i].tired;<br /> // _count--;<br /> // }<br /> // }<br /> // return false;<br /> //}<br /> int main() {<br /> //freopen("1.txt", "r", stdin);<br /> while(cin >> n >> k) {<br /> for(int i = 0; i < n; i++) scanf("%d", &a[i]);<br /> sort(a, a + n);<br /> //for(int i = 0; i < n - 1; i++) {<br /> // data[i].x = i;<br /> // data[i].y = i + 1;<br /> // data[i].tired = (a[i] - a[i + 1]) * (a[i] - a[i + 1]);<br /> //}<br /> //sort(data, data + n - 1, cmp);<br /> //memset(isVis, false, sizeof(isVis));<br /> //ans = _count = 0;<br /> //dfs(0);<br /> //cout << ans << endl;<br /> memset(tired, 0, sizeof(tired));<br /> tired[2][1] = (a[0] - a[1]) * (a[0] - a[1]);<br /> for(int i = 3; i <= n; i++) {<br /> for(int j = 1; j <= i / 2 && j <= k; j++) {<br /> if(i - 1 >= j * 2)<br /> tired[i][j] = min(tired[i - 1][j], tired[i - 2][j - 1] + (a[i - 1] - a[i - 2]) * (a[i - 1] - a[i - 2]));<br /> else<br /> tired[i][j] = tired[i - 2][j - 1] + (a[i - 1] - a[i - 2]) * (a[i - 1] - a[i - 2]);<br /> }<br /> }<br /> cout << tired[n][k] << endl;<br /> }<br /> return 0;<br /> }