ZOJ 1234 Chopsticks (线性dp)

OJ题目：click here~~~

题目分析：N个数，选出k个组合，这里N>=K。 保证每个组合中第三个一定是最大的，求所有组合的另两个数的差的平方和的最小值。给的初始N个数是非递减序列。

明显感觉每个组合中的前两个数应该是连着的，同样可以通过证明得到。设状态dp[ i ][ j ] 为第i个数到第n个数，构成j个组合的最小目标值。则

dp[ i ][ j ] = min(dp[ i + 1 ][ j ] , dp[i + 2][ j - 1] + mut(num[i - 1] - num[ i ]) )

AC_CODE

int num[5002] , dp[5002][1008];
int mul(int a)
{
    return a*a;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int k , n , i , j;
        cin >> k >> n;
        k += 8;
        for(i = 1;i <= n;i++)
        {
            scanf("%d",num+i);
        }
        memset(dp , 0 , sizeof(dp));
        dp[n - 2][1] = mul(num[n - 1] - num[n - 2]);
        for(i = n - 3;i >= 1;i--)
        {
            for(j = 1;j <= k;j++)
            {
                if((n - i + 1) < 3*j) continue;
                if((n - i + 1) == 3*j)
                    dp[i][j] = dp[i+2][j-1] + mul(num[i]-num[i+1]);
                else
                    dp[i][j] = min(dp[i+1][j] , dp[i + 2][j - 1] + mul(num[i+1] - num[i]));
            }
        }
        cout << dp[1][k] << endl;
    }
    return 0;
}