首页 > 代码库 > NYIST 1108 最低的惩罚
NYIST 1108 最低的惩罚
最低的惩罚
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
那么现在问题就来了。。。
给你N(1=<N<=15)个任务,每个任务有一个截止完成时间t(1=<t<=10^8)和完成该任务需要的天数v(1=<v<=10^8),任务每超时一天惩罚加1,问最少能获得多少惩罚?
- 输入
- 第一行一个数T,表示测试数据组数(T<2000);
对于每组测试数据,第一行一个数N,表示任务个数;
紧接着N行,每行两个数t和v,如上所述。 - 输出
- 对于每组测试数据,输出最小惩罚。
- 样例输入
233 320 13 233 36 36 3
- 样例输出
23
- 上传者
- TC_赵坤垚
- 解题:状压dp,老王说的,确实是的
- View Code
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 16;18 int n,dp[1<<maxn],cnt[1<<maxn],td[maxn],tm[maxn];19 int main() {20 int T;21 scanf("%d",&T);22 while(T--){23 scanf("%d",&n);24 int u = 1<<n;25 for(int i = 0; i < n; ++i)26 scanf("%d %d",td+i,tm+i);27 memset(dp,0x3f,sizeof(dp));28 for(int i = 0; i < n; ++i)29 dp[1<<i] = tm[i] > td[i]?tm[i] - td[i]:0;30 for(int i = 1; i < u; ++i){31 cnt[i] = 0;32 for(int k = 0; k < n; ++k)33 if(i&(1<<k)) cnt[i] += tm[k];34 }35 for(int i = 1; i < u; ++i){36 for(int k = 0; k < n; ++k){37 if(i&(1<<k)) continue;38 int tmp = cnt[i] + tm[k] - td[k];39 if(tmp > 0) dp[i^(1<<k)] = min(dp[i^(1<<k)],dp[i] + tmp);40 else dp[i^(1<<k)] = min(dp[i^(1<<k)],dp[i]);41 }42 }43 printf("%d\n",dp[u-1]);44 }45 return 0;46 }
NYIST 1108 最低的惩罚
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。