UVALive - 6952 （隔板dp）

UVALive - 6952

题目大意：超市最近有活动，购买的商品在最后支付时四舍五入，为了使支付的金钱最少，给买的商品进行分组，要求不准对这些商品排序。

解题思路：其实就是给一组数，将这组数插隔板，即隔板dp，dp[i][j]记录的是当有i个数，j个隔板时最少钱。转移方程为dp[i][j] = min(dp[i-1][j-1]+a[i], dp[i-1][j] + a[i])，意思是当有i个数时，是在i前放个隔板（j-1隔板拿到i前），还是不放隔板。当j== i-1时说明j是最后一个隔板，只能放到i前。

还有就是保证最优，输入5 5   5 5 5 5 5，输出30，虽然要分五组，但是3组是最优的，所以输出30。

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <queue>
#include <vector>
#include <map>

using namespace std;

const int inf = 0x3f3f3f3f;
const int Max = 2017;
typedef long long  LL;
int a[Max], b[Max], dp[Max][Max];

int main()
{
    int n, x, k, i, j, d;
    while(cin>>n>>d)
    {
        memset(dp, inf, sizeof dp);
        dp[0][0] = 0;
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            dp[i][0] = a[i]+dp[i-1][0];
        }
        for(i = 1; i <= n; i++)
        {
            for(j = 1; j < d+1&&j < i; j++)
            {
                if(j == i-1)
                    dp[i][j] = (dp[i-1][j-1] +5)/10*10+ a[i];
                else
                    dp[i][j] = min((dp[i-1][j-1] +5)/10*10+ a[i], dp[i-1][j] + a[i]);
            }
        }
        int ans = inf;
        for(i = 0; i <= d; i++)
        {
            ans = min(ans, (5+dp[n][i])/10*10);
        }
        printf("%d\n", ans);
    }
    return 0;
}
/*
5 2
1 1 1 1 1
5 1
13 21 55 60 42
7 1
2 2 2 1 3 5 6
7 2
2 2 2 1 3 5 6
7 3
2 2 2 1 3 5 6
7 1
9 2 2 2 2  2 9
7 2
9 2 2 2 2 2 9
7 3 
9 2 2 2 2 2  9

 */