CodeForcesGym 100676G Training Camp
G. Training Camp
This problem will be judged on CodeForcesGym. Original ID: 100676G
64-bit integer IO format: %I64d Java class name: (Any)
Montaser is planning to train very hard for ACM JCPC 2015; he has prepared a list with n topics
to study in the next n days, one topic every day. Montaser knows that some topics depend on other topics, so he asked coach Fegla and got a list
of m constraints on the order in which he should study these topics. Also, coach Fegla told him that when he studies topic x on the kth day (1 ≤ k ≤ n), his level will
increase by k*Wx, where Wx is a weight for topic x, representing how hard it is. Given the list of topics, the weight of each topic, and the list of constrains, can you tell Montaser
what is the maximum level he can reach in these n days? He is currently at level 0.
Input
The first line of input contains one integer T representing the number of test cases (1 ≤ T ≤ 128).
The first line of each test case contains two integers: n and m (1 ≤ n ≤ 18).
The next n lines, each contains the title of one of the topics followed by a space, then an integer
W that represents the weight of this topic (1 ≤ W ≤ 100).
The next m lines are of the form: Topic 1 --> Topic 2, which means that Topic 1 must be studied
before Topic 2.
Titles contain only English letters and spaces (no more than 40 characters).
Test cases are separated by a blank line.
Output
For each test case, print the maximum level that Montaser can reach.
Sample Input
1
3 2
Implementation 3
Dynamic Programming 10
Greedy 7
Greedy --> Dynamic Programming
Implementation --> Dynamic Programming
Sample Output
解题:状压动规
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int n,m,w[maxn],son[maxn],fa[maxn];
vector<int>g[maxn];
vector<int>o[maxn];
unordered_map<string,int>ump;
void read(char *str,int pos){
int len = strlen(str)-,ret = ;
while(len >= && isdigit(str[len])) --len;
char topic[];
strncpy(topic,str,len);
topic[len] = '\0';
for(int i = len + ; str[i]; ++i)
ret = ret* + str[i] - '';
ump[topic] = pos;
w[pos] = ret;
}
void read2(char *str,int &a,int &b){
int len = strlen(str) - ;
while(len >= && str[len] != '>') --len;
char topic[];
strncpy(topic,str,len-);
topic[len-] = '\0';
a = ump[topic];
strcpy(topic,str + len + );
b = ump[topic];
}
int dfs(int u,vector<int>(&h)[maxn]){
int ret = ;
for(int i = h[u].size()-; i >= ; --i){
ret |= (<<h[u][i]);
ret |= dfs(h[u][i],h);
}
return ret;
}
int dp[<<maxn],day[<<maxn];
int calc(int st){
if(day[st] != -) return day[st];
int x = st;
st = (st&0x55555555) + ((st>>)&0x55555555);
st = (st&0x33333333) + ((st>>)&0x33333333);
st = (st&0x0F0F0F0F) + ((st>>)&0x0F0F0F0F);
st = (st&0x00FF00FF) + ((st>>)&0x00FF00FF);
st = (st&0x0000FFFF) + ((st>>)&0x0000FFFF);
return day[x] = st;
}
int main(){
int kase,a,b;
char str[];
scanf("%d",&kase);
while(kase--){
scanf("%d%d",&n,&m);
ump.clear();
getchar();
for(int i = ; i < n; ++i){
g[i].clear();
o[i].clear();
gets(str);
read(str,i);
fa[i] = son[i] = ;
}
for(int i = ; i < m; ++i){
gets(str);
read2(str,a,b);
g[a].push_back(b);
o[b].push_back(a);
}
memset(dp,,sizeof dp);
memset(day,-,sizeof day);
for(int i = ; i < n; ++i){
son[i] = dfs(i,g);
fa[i] = dfs(i,o);
}
m = (<<n);
for(int i = ; i < m; ++i){
for(int j = ; j < n; ++j){
if(((i>>j)&)) continue;
if(!(son[j]&i) && (fa[j]&i) == fa[j])
dp[i|(<<j)] = max(dp[i|(<<j)],dp[i] + (calc(i) + )*w[j]);
}
}
printf("%d\n",dp[m-]);
}
return ;
}
最新文章
- Android开发自学笔记(Android Studio)&mdash;4.界面编程与View组件简单介绍
- 项目公共js(vue.js)
- 犀利点评:csdn某文<;第一次创业还是失败了---分享失败的经验>;
- 定制Eclipse IDE之功能篇(二)
- 【python】os模块
- [改善Java代码]警惕自增的陷阱
- bzoj1662: [Usaco2006 Nov]Round Numbers 圆环数
- 在mac os下编译android -相关文章
- 第十七章——配置SQLServer(4)——优化SQLServer实例的配置
- 【Windows 10 应用开发】输入模拟
- 如何相互转换逗号分隔的字符串和List
- 基于Python实现matplotlib中动态更新图片(交互式绘图)
- ES6 new syntax of Arrow Function
- Nginx 配置HTTPS 与Node.js 配置HTTPS方法
- java的Integer与int的比较
- c/c++ 重载运算符 基本概念
- 【原创】IDEA一定要改的八条配置
- 一、IntelliJ IDEA创建java项目
- 20165337岳源 预备作业3:Linux安装及命令入门
- TF:利用TF的train.Saver载入曾经训练好的variables(W、b)以供预测新的数据—Jason niu