hdu1421 搬寝室
简单dp
把重物按质量大小排序
一个物品只有可能跟其质量相邻的物品一起拿 质量差的平方才最小
dp[i][j]表示在前 i 个物品中取 j 对所需最小疲劳度
dp方程:dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(wi-w[i-1])*(wi-w[i-1]));
看取或者不取前两个物品的疲劳度大小
#include<iostream> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; #define inf 2147483646 int dp[2005][1005],n,k,i,j,w[2005],tmp; int main() { dp[0][0]=0; w[0]=0; while(~scanf("%d%d",&n,&k)) { for(i=1;i<=n;i++) scanf("%d",&w[i]); sort(w+1,w+n+1); for(i=0;i<=n;i++) for(j=1;j<=k;j++) dp[i][j]=inf; for(i=2;i<=n;i++) { for(j=1;2*j<=i;j++) { tmp=w[i]-w[i-1]; dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+tmp*tmp); } } printf("%d\n",dp[n][k]); } return 0; }
补充:软件开发 , C++ ,