现在的位置: 首页 > 综合 > 正文

(中等) 状态压缩dp HOJ 2193 Time to Graduate

2014年09月05日 ⁄ 综合 ⁄ 共 4271字 ⁄ 字号小中大 ⁄ 评论关闭

Time to Graduate

My Tags	(Edit)

	Source : The 2005 ACM Pacific Northwest Programming Contest
	Time limit : 5 sec		Memory limit : 32 M

Submitted : 47, Accepted : 22

A prospective CS student is investigating how many semesters it will take to graduate from a variety of different universities. Each university provides a list of required courses, their prerequisites, and when each course is offered. Given this information, determine the minimum number of semesters to graduate.

Consider the following example. A student is required to take 4 courses, mt42, cs123, cs456, and cs789. mt42 is only offered in the fall semester and has no prerequisites. Similarly, cs123 is only offered in the spring semester and has no prerequisites. cs456 is only offered in the spring semester and has both cs123 and mt42 as prerequisites. Finally, cs789 is offered in both fall and spring and has cs456 as its only prerequisite. The shortest time to graduate is 5 semesters, by taking mt42 in the fall, cs123 in the next spring, cs456 the following spring (since it is not offered in the fall) and finally cs789 the following fall.

For this problem, there are only two semesters, fall and spring. Always start counting semesters from the fall.

In addition to the fall/spring scheduling issues, there is one slight complication. In order to keep the dormitories full, each university limits the number of courses that can be taken in any semester. This limit appears as part of the input data. The third example below illustrates this issue.

Input

There are one to twenty-five data sets, followed by a final line containing only the integers -1 -1. A data set starts with a line containing two positive integers n, 1 <= n <= 12, which is the number of courses in this data set and m, 2 <= m <= 6, which is the maximum number of courses that can be taken in any single semester. The next line contains the n course identifiers. Each is a 1-5 character string from the set {a-z, 0-9}. Following the course identifiers is the individual course information. This consists of n lines, one line for each course, containing the course identifier, semester offered ('F'=Fall, 'S'=Spring, 'B'=Both semesters), the number of prerequisite courses, p, 0 <= p <= 5, and finally p prerequisite course identifiers. The first example data set below corresponds to the problem described above.

Output

The output contains one line for each data set, formatted as shown in the sample output.

Sample Input

4 6
cs123 mt42 cs456 cs789
mt42 F 0
cs123 S 0
cs456 S 2 cs123 mt42
cs789 B 1 cs456
3 6
math1 comp2 comp3
comp3 S 1 comp2
math1 S 0
comp2 F 1 math1
4 3
m10 m20 c33 c44
m10 B 0
m20 B 0
c33 B 0
c44 B 0
-1 -1

Sample Output

The minimum number of semesters required to graduate is 5.
The minimum number of semesters required to graduate is 4.
The minimum number of semesters required to graduate is 2.

题意：我要尽早毕业，已经知道需要学N门课才能毕业，每门科目有一定要求，有的要在fall学期才能上，有的要在spring学期才能上，有的两个学期都能上，有的要求先学完某些课程才能上。问最少要多少个学期才能毕业。。。

思路：我们用dp[i][s]=true 表示在第i学期能到达s状态，我们由dp[i][s]可以推出dp[i+1]的状态，这个状态我们用深搜就行了，因为m不大，最多才6，穷举也不会太大。直到dp[i][(1<<n)-1]为true，表示学完了，可以毕业了！！！

代码：

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

#include<map>

using namespace std;

#define max(a,b) (a) < (b) ? (b) : (a)

#define LL long long

#define eps 1e-8

const int maxn = (1<<12)+10;

const int inf = 1e9;

bool dp[2][maxn];

int pre[15];

map<string,int> course;

int p[15] , n , m , sem[15];

char buffer[10];

string s;

void init()

{

course.clear();

memset(pre,0,sizeof(pre));

}

void input()

{

for (int i = 1 ; i <= n ; ++i)

{

scanf("%s",buffer);

s = buffer;

course[s] = i;

}

for (int i = 0 ; i < n ; ++i)

{

scanf("%s",buffer);

int x = course[s=buffer];

scanf("%s",buffer);

if (buffer[0]=='B') sem[x] = 2;

else if (buffer[0]=='F') sem[x] = 1;

else if (buffer[0]=='S') sem[x] = 0;

int k;

scanf("%d",&k);

while (k--)

{

int y;

scanf("%s",buffer);

y = course[s=buffer];

pre[x] += p[y];

}

void dfs(int prer,int state,int cur,int rest,int pos,int term)

{

dp[pos][state] = true;

if (rest==0 || cur > n) return;

if ((pre[cur]&prer)==pre[cur] && !(state&(p[cur])) && (sem[cur]==2 || (term%2)==sem[cur]) ) dfs(prer,state+p[cur],cur+1,rest-1,pos,term);

dfs(prer,state,cur+1,rest,pos,term);

}

void solve()

{

int max_s = 1<<n;

memset(dp,false,sizeof(dp));

dp[1][0]= true;

int cnt;

for (cnt = 1 ; ; ++cnt)

{

for (int s = 0 ; s < max_s ; ++s)

{

if (!dp[cnt%2][s]) continue;

dfs(s,s,1,m,(cnt+1)%2,cnt);

}

if (dp[(cnt+1)%2][max_s-1]) break;

memset(dp[cnt%2],false,sizeof(dp[cnt%2]));

}

printf("The minimum number of semesters required to graduate is %d.\n",cnt);

}

int main()

{

p[1] = 1;

for (int i = 2 ; i <= 12 ; ++i) p[i] = p[i-1]<<1;

while (scanf("%d%d",&n,&m)==2)

{

if (n==-1 && m==-1) return 0;

init();

input();

solve();

}

题后语：毕业真难啊，我们现在的学习就是应付式的学习，课堂上学的是不是自己想学的，甚至和自己专业没有什么关系的，但为了那单薄的毕业证却要费这么多心思去“搞定”它，看题目里就是问最少要多少个学期才能毕业，多悲哀啊，现在的教育为什么会让学生钻尽孔子，绞尽脑汁，运用自己强大的计算能力，一点点的算计着怎么样才能更快毕业，这种教育不就让我们的功利心不断加强吗？我相信学习并不是那么痛苦的，痛苦的是学习自己不喜欢的东西。要在什么时候，我才能看到学生们是主动的去学习，而不是被这些束缚着，痛恨学习。。。

【上篇】Excel Vba GetObject 如何保存Excel文件
【下篇】tomcat 启动运行指定类

作者: zjffly2000

该日志由 zjffly2000 于10年前发表在综合分类下，最后更新于 2014年09月05日.
转载请注明: (中等) 状态压缩dp HOJ 2193 Time to Graduate | 学步园 +复制链接

抱歉!评论已关闭.

学步园

(中等) 状态压缩dp HOJ 2193 Time to Graduate

Time to Graduate

作者: zjffly2000

书签

最新文章New

本站推荐

返回首页