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

 */