题意:从n根筷子中选出3*(k+8)根筷子,组成k+8组,每组3根,每组的badness值为最短两根长度之差的平方。求最小的badness值。
分析:这本是个很简单的题,但我一直脑残总想着顺推,想了各种方法处理第三根筷子,发现都不行。其实逆着推就可以保证每组都能找到最长的那根筷子了。 dp[i][j]表示从第i根到第n根组成了j组的最小值,则有dp[i][j]=min(dp[i+1][j],dp[i+2][j-1]+(a[i+1]-a[i])*(a[i+1]-a[i]))。注意当n-i+1==3*j时,dp[i][j]是直接等于dp[i+2][j-1]+(a[i+1]-a[i])*(a[i+1]-a[i])的,因为这时不能再舍弃第i根筷子不用了。
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define inf 2000000000
int dp[5010][1010],n,k,a[5010];
int main()
{
int t,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&k,&n);
k+=8;
for(i=1;i<=n;i++) scanf("%d",a+i);
for(i=n;i>=1;i--) dp[i][0]=0;
for(i=n;i>=n-1;i--) // 初始化
{
for(j=1;j<=k;j++) dp[i][j]=inf;
}
for(i=n-2;i>=1;i--)
{
for(j=1;j<=k&&n-i+1>=3*j;j++)
{
if(n-i+1>3*j) dp[i][j]=min(dp[i+1][j],dp[i+2][j-1]+(a[i+1]-a[i])*(a[i+1]-a[i]));
else dp[i][j]=dp[i+2][j-1]+(a[i+1]-a[i])*(a[i+1]-a[i]);
}
}
printf("%d\n",dp[1][k]);
}
return 0;
}