我的第一个dp程序 哎! 可惜状态方程不是自己想的 有点小小的遗憾!!
搬寝室
Total Submission(s) : 107 Accepted Submission(s) : 40
2 1 1 3
4
状态方程
dp[k][i]=min(dp[k-1][i-2]+(a[i]-a[i-1])^2,dp[k][i-1]);
dp[k][i] 表示 k 对物品在前 i 个物品的最小值
代码:
#include<iostream> #include<stdio.h> #include<algorithm> #define N 2005 using namespace std; int dp[N/2][N]; int a[N]; void Init(int k) { int i; dp[k][2*k]=0; for(i=2;i<=2*k;i+=2) dp[k][2*k]+=(a[i]-a[i-1])*(a[i]-a[i-1]); } int work(int n,int m) { int i,k; sort(a+1,a+n+1); for(k=1;k<=m;k++) Init(k); for(k=1;k<=m;k++) { for(i=2*k+1;i<=n;i++) { if((dp[k-1][i-2]+(a[i]-a[i-1])*(a[i]-a[i-1]))<dp[k][i-1]) dp[k][i]=dp[k-1][i-2]+(a[i]-a[i-1])*(a[i]-a[i-1]); else dp[k][i]=dp[k][i-1]; } } return dp[m][n]; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { int i; for(i=1;i<=n;i++) cin>>a[i]; int ans=work(n,k); printf("%d\n",ans); } return 0; }