首页 > 代码库 > HNU 12961 BitTorrent DP
HNU 12961 BitTorrent DP
题意:
你在网上下载东西,一个文件存储在一段或者多段里面,问怎么选择能在规定的流量内下载最多的文件数量。每段的大小一样。
思路:
习惯了做答案保存在DP数组里的题,做这种答案保存在下标里的题,转不过弯来。开始想过背包,但是一来内存不够,二来时间也不够。
其实是这样做的,dp[i][j][0/1]保存枚举到第i个,下载了j个,最后一个是否被下载的最小花费。 最后找花费没超过限制的最大值就好了。
最后值得注意的是,最后一段的时候,可能不会被p整除,不要算多了哦。
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 const int INF = 1<<30;20 const int MAXN = 3055;21 22 int dp[MAXN][MAXN][2]; //dp[i][j][k] 表示取到第i个,取了j个,的时候,第i个取或者不取23 int a[MAXN];24 int sum[MAXN]; //前缀和25 int n, p, l;26 27 int main() {28 #ifdef Phantom0129 freopen("HNU12961.in", "r", stdin);30 #endif //Phantom0131 32 while (scanf("%d%d%d", &n, &p, &l)!=EOF) {33 if (n==0&&p==0&&l==0) break;34 35 sum[0] = 0;36 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);37 for (int i = 1; i <= n; i++) sum[i] = sum[i-1]+a[i];38 for (int i = 0; i <= n; i++)39 for (int j = 0; j <= n; j++)40 dp[i][j][0] = dp[i][j][1] = INF;41 dp[0][0][0] = 0;42 43 for (int i = 1; i <= n; i++) {44 for (int j= 0; j <= i; j++)45 dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]);46 for (int j = 1; j <= i; j++)47 dp[i][j][1] = min(dp[i-1][j-1][0]-(sum[i-1]/p)*p,48 dp[i-1][j-1][1]-((sum[i-1]+p-1)/p)*p)49 + (i==n ? sum[i] : ((sum[i]+p-1)/p)*p);50 }51 int ans = 0;52 for (int i = 0; i <= n; i++)53 if (dp[n][i][0]<=l || dp[n][i][1]<=l)54 ans = max(ans, i);55 printf("%d\n", ans);56 }57 58 return 0;59 }
HNU 12961 BitTorrent DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。