首页 > 代码库 > uva 473(dp)

uva 473(dp)

题意:按创作时间给出n首歌每首歌的时间ti,然后按创作时间装到m个光盘内,给出光盘最大分钟数t,问m个光盘最多总共放多少首歌。
题解:对于每首歌都能够选或者不选,假设选择了这首歌,是否把这首歌当做第j张光盘的第一首歌。

f[i][j][k]表示前i首歌放到第j张光盘里用分钟数是k的容量最多放多少首歌。
f[i][j][k] = f[i - 1][j][k]表示要选这首歌
f[i][j][k] = max(f[i][j][k], f[i][j - 1][t] + 1)表示把这首歌当做第j张光盘的第一首歌
f[i][j][k] = max(f[i][j][k], f[i][j][k-a[i]] + 1)表示不选这首歌当第j张光盘第一首歌
假设用二维滚动数组取代第一维,j要逆序枚举。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1000;
int n, m, t, f[N][N], a[N];

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        memset(f, 0, sizeof(f));
        scanf("%d%d%d", &n, &t, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d%*c", &a[i]);
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                for (int k = t; k >= a[i]; k--) {
                    f[j][k] = max(f[j][k], f[j - 1][t] + 1);
                    f[j][k] = max(f[j][k], f[j][k - a[i]] + 1);
                }
            }
        }
        printf("%d\n", f[m][t]);
        if (cas)
            printf("\n");
    }
    return 0;
}
<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

uva 473(dp)