現在的位置: 首頁 > 綜合 > 正文

(中等) 狀態壓縮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

本站推薦

返回首頁