UVA 473——Raucous Rockers

痛定思痛。 2022-07-28 08:41 9阅读 0赞

题意：给定n个数，放到m个容器里，每个容器的容量是t（n个数的累加和不超过t），在不打乱放的顺序的情况下问最多能放多少个数？

思路：多维dp，f\[i\]\[j\[k\]表示前i个数放到第j个容器放k个的最大数量。则不放的状态为f\[i-1\]\[j\]\[k\],放为f\[i-1\]\[j-1\]\[k\](放在第一个）f\[i-1\]\[j-1\]\[k-v\[i\]\]+1(不是放在第一个）。

code:

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1005;
    int v[N],f[N][120][120];
    
    int main()
    {
        int T,n,m,t,x;
        scanf("%d",&T);
        while (T--){
            scanf("%d%d%d",&n,&t,&m);
            int len=0;
            for (int i=1;i<=n;i++)
            {
                if (i==1) scanf("%d",&x);
                else scanf(",%d",&x);
                if (x<=t) v[++len]=x;
            }
            n=len;
            memset(f,0,sizeof(f));
            for (int i=1;i<=n;i++)
                for (int j=1;j<=m;j++)
                    for (int k=0;k<=t;k++){
                        f[i][j][k]=f[i-1][j][k];
                        if (k>=v[i]){
                            f[i][j][k] = max(f[i][j][k], f[i-1][j][k-v[i]]+1);
                            f[i][j][k] = max(f[i][j][k], f[i-1][j-1][t]+1);
                        }
                    }
            printf("%d\n",f[n][m][t]);
            if (T) puts("");
        }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_回溯_中等_473.火柴拼正方形

目录 1.题目 2.思路 3.代码实现（Java） 1.题目你将得到一个整数数组 matchsticks ，其中 matchsticks\[i

太过爱你忘了你带给我的痛/ 2023年10月06日 23:38/ 0 赞/ 22 阅读

相关 473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the l

灰太狼/ 2023年07月06日 14:59/ 0 赞/ 7 阅读

相关【递归】 LeetCode473. 火柴拼正方形

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

梦里梦外;/ 2022年12月03日 05:22/ 0 赞/ 200 阅读

相关 leetcode 473. Matchsticks to Square | 473. 火柴拼正方形（递归）

题目 [https://leetcode.com/problems/matchsticks-to-square/][https_leetcode.com_problems

太过爱你忘了你带给我的痛/ 2022年09月09日 09:55/ 0 赞/ 154 阅读

相关 473-Unix/Linux上的五种I/O模型

Unix/Linux上的五种I/O模型 I/O模式是操作系统上任何的I/O，内存I/O，磁盘I/O，网络I/O都可以应用。我们主要考虑网络I/O。阻塞 blo

男娘i/ 2022年09月08日 00:12/ 0 赞/ 119 阅读

相关 UVA 473——Raucous Rockers

题意：给定n个数，放到m个容器里，每个容器的容量是t（n个数的累加和不超过t），在不打乱放的顺序的情况下问最多能放多少个数？思路：多维dp，f\[i\]\[j\[

痛定思痛。/ 2022年07月28日 08:41/ 0 赞/ 10 阅读

相关 Codeforces Round 473-2B题解报告

题目 [http://codeforces.com/contest/959/problem/B][http_codeforces.com_contest_959_prob

曾经终败给现在/ 2022年05月28日 11:48/ 0 赞/ 205 阅读

相关 UVA 414

include<iostream> include<string> include<cstring> using namespace std;

╰半夏微凉°/ 2021年11月17日 21:36/ 0 赞/ 299 阅读

相关 UVA 621

include<iostream> include<string> using namespace std; int main() {

朴灿烈づ我的快乐病毒、/ 2021年11月17日 21:33/ 0 赞/ 253 阅读

相关 Uva 540

include<iostream> include<queue> include<cstring> include<string> us

Love The Way You Lie/ 2021年11月17日 21:20/ 0 赞/ 342 阅读