牛客網(wǎng)

文章目錄

• • 題目描述
  • 題解：
  • 代碼：

題目描述

Rabbit通過了上次boss的考核，現(xiàn)在她又遇到了一個(gè)問題。 Rabbit接到了K個(gè)任務(wù)，每個(gè)任務(wù)她可以自由選擇用i天去完成(1≤ i≤
N)。刁鉆的boss想讓Rabbit恰好用W天完成所有任務(wù)。
已知Rabbit用i天完成一個(gè)任務(wù)能讓boss獲得的滿意度為vi(因?yàn)橥瓿扇蝿?wù)的質(zhì)量不同)，她想知道在滿足boss要求的情況下能讓boss獲得的總滿意度最大是多少。

輸入描述:
第一行三個(gè)整數(shù)N，K，W。
第二行N個(gè)整數(shù)vi，vi表示用i天完成一個(gè)任務(wù)能讓boss獲得的滿意度。
輸出描述:
輸出Rabbit在滿足boss要求的情況下能讓boss獲得的總滿意度最大是多少。
示例1
輸入

3 3 5 6 2 4

輸出

16

說明

Rabbit可以選擇分別用1天，1天，3天完成這三個(gè)任務(wù)，最大滿意度為6+6+4=16

備注:

2≤ N,K≤ 2000,K≤ W≤ min(4000,2*K) 0<vi≤ 10000

題解：

不難看出是一個(gè)背包問題
我們想想背包問題有幾個(gè)要素：物品花費(fèi)（本題中為天數(shù)），物品價(jià)值（本題為滿意度），物品數(shù)量，總?cè)莘e（本題為W天）。你會(huì)發(fā)現(xiàn)我沒有標(biāo)物品數(shù)量，那是因?yàn)樵谶@個(gè)題里面物品只有總數(shù)量，也就是總?cè)蝿?wù)數(shù)K，卻沒有單個(gè)物品的數(shù)量。這咋整，怎么才能把數(shù)量這個(gè)限制給去掉？
我們可以這么想，一共有K個(gè)任務(wù)，那我們先給每個(gè)任務(wù)分配一天，一共用掉K天，因?yàn)槲覀円蟮赪天正好完成，所以還剩下W-K天沒有分配，而剩下這些天數(shù)可以隨便分配，沒有數(shù)量限制（因?yàn)橐粋€(gè)任務(wù)最少要1天，而我們上來就給了每個(gè)任務(wù)一天，所以給分配時(shí)，無需考慮是否有任務(wù)沒做）
無數(shù)個(gè)W-K天，不就成完全背包問題了嗎？
注意給的滿意度是指i天對(duì)應(yīng)的滿意值，而非第i天，所以我們要先處理一下，將每天的滿意值減去第一天滿意值（相當(dāng)于第一天已分配）。
最后再加上即可

代碼：

#include <bits/stdc++.h> using namespace std; int dp[4010], a[2010]; int main() {int n, k, w;//可用天數(shù)，任務(wù)數(shù)量，容量 scanf("%d %d %d", &n, &k, &w);memset(dp,-0x3f,sizeof(dp));dp[0] = 0;scanf("%d", &a[0]);for(int i = 1; i < n; i++) {scanf("%d", &a[i]);a[i] -= a[0];//與第一天的差 }w -= k;//for(int i = 1; i < n; i++) {//無窮背包 for(int j = i; j <= w; j++) {dp[j] = max(dp[j-i] +a[i],dp[j]);}}printf("%d\n", dp[w]+k*a[0]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Rabbit的工作(2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。