這場只出了一道題，掉了很多分。D題和E題近期補上。
A
題目描述：
有N(N<200)項工作。每項工作必須在一個模式下花費1個單位時間完成，工作之間的完成順序存在依賴關系，形成DAG圖。一共有三種模式(0,1,2)。模式之間的切換時間為
[0,1,2]
[2,0,1]
[1,2,0]
一開始你可以0花費選擇一種模式，問完成所有工作的最少時間。
算法分析：
拓撲排序+貪心法。
假設我目前在模式A，那么第一步一定要一口氣把A模式的任務全都完成。
然后要選擇模式切換代價較小的模式。因為這樣的模式最多只有一種，所以就可以輕松解決了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int flag[3][3] = {
{0,1,2},{2,0,1},{1,2,0}
};
const int N = 205;
int num[N] , G[N][N], Du[N], tmp[N],vis[N],n;
int work(
int p){
// cout<<"p: "<<p<<endl;
int v = 0,f = 0;
while(1){
f = 0;
for(
int i=0;i<n;i++)
if(!Du[i] && !vis[i] && num[i] == p){
// cout<<i<<" ";
vis[i] = 1;
v++;
for(
int v=0;v<n;v++)
if(!vis[v] && G[i][v])
Du[v]--;
f = 1;
}
if(!f)
break;
}
// cout<<endl;
for(
int i=0;i<n;i++)
if(!Du[i] && !vis[i] && flag[p][num[i]] == 1){
v += 1 + work(num[i]);
return v;
}
for(
int i=0;i<n;i++)
if(!Du[i] && !vis[i]) {
v += 2 + work(num[i]);
return v;
}
return v;
}
int main(){
while( cin >> n){
for(
int i=0;i<n;i++)
for(
int j=0;j<n;j++)
G[i][j] = 0;
for(
int i=0;i<n;i++){
scanf("%d",&num[i]);
num[i]--;
}
int t;
memset(tmp,0,
sizeof(tmp));
for(
int i=0;i<n;i++){
cin >> tmp[i];
for(
int oo=0;oo<tmp[i];oo++){
int u;
cin >> u;
u --;
G[u][i] = 1;
}
}
int ans = ~0u>>2;
for(
int p=0;p<3;p++)
for(
int i=0;i<n;i++)
if(!tmp[i] && p == num[i]){
memset(vis,0,
sizeof(vis));
for(
int i=0;i<n;i++) Du[i] = tmp[i];
int v =work(p);
// cout<<"ans: "<<p<<" "<<v<<endl;
if(v<ans) ans = v;
break;
}
cout<< ans << endl;
}
}
B
給出一個序列a[10](a[i]<100)，和N(N<100)。構造一個長度為N的數字，要求
1.沒有前導0
2.數字i不少于a[i]個
求構造方法數。
算法分析：
典型的動態規劃求解。
dp[i][j]表示前j個數字構成符合條件的長度為i的數字的方法數。
顯然dp[i][j] = sum(dp[k][j-1] * C[i][k]) 其中k>0 && k<=i-a[j]
組合數預處理出來即可，其中要考慮轉移0的問題，這個留給大家思考吧~~
#include<iostream>
#include<cstdio>
using namespace std;
const int mod = (
int)1e9 + 7;
typedef
long long ll;
const int N = 105;
ll C[N][N];
void OP(
int msk){
for(
int i=0;i<10;i++, msk>>=1)
cout<<(msk&1);cout<<" ";
}
int main(){
for(
int i=0;i<N;i++) {
C[i][0] = 1;
for(
int j=1;j<=i;j++)
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
int n, a[11];
static ll dp[N][1<<11];
while(cin >> n){
for(
int i=0;i<10;i++){
cin >> a[i];
}
dp[0][0] =1;
for(
int i = 0; i<=n; i++){
for(
int msk = 1; msk < (1<<10); msk++){
ll &t = dp[i][msk] ;
t = 0;
for(
int p = 0; p < 10; p++)
if((1<<p) & msk){
ll s = 0;
for(
int j=0;j<=i-a[p];j++){
if(p) s += C[i][i-j] * dp[j][msk^(1<<p)];
else s += i ?C[i-1][i-j]*dp[j][msk^(1<<p)] : 0;
s %= mod;
if(s){
// cout<<i<<" ";OP(msk);cout<<j<<" "<<p<<" "<<dp[j][msk^(1<<p)]<<endl;
// cout<<s<<endl;
}
}
t = (t+s) % mod;
break;
}
}
}
ll ans = 0;
for(
int i = 1; i<=n; i++)
ans = (ans + dp[i][(1<<10)-1]) % mod;
cout<< ans << endl;
}
}
C
給一個N*N的矩陣(N<300)，權值范圍是[-1000,1000]。現在讓你從右上角走到左下角，只能向下或者向右走，走兩次，每個格子最多取一次權值，問最大能取到的值是多少。
算法分析:
因為格子上的權值可能是負數，所以費用流ggg。
考慮動態規劃，想像兩次是兩個人a,b同時走的，在走了i步之后,a的x值是xa，b的x值是xb。
dp[i][xa][xb]記為此時可以獲取的最大權值。
轉移就很簡單了，呵呵~
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 305;
int dp[2][N][N], num[N][N],n;
const int inf = ~0u>>2;
inline bool chk(int x,int y){
return x >=0 && y >=0 && x <n && y <n;
}
inline void chkmax(int &a,const int b){if(a<b)a=b;}
int main(){
while(cin >> n){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin >> num[i][j] ;
int ans = (dp[0][0][0] = num[0][0]);
for(int i=1;i<2*n-1;i++)
for(int p = (i>=n)? i-n+1: 0; p < min(n,i+1); p++) {
for(int q = p; q< min(n,i+1); q++) {
int v;
if(q == p) v = num[p][i-p];
else v = num[p][i-p] + num[q][i-q];
dp[i&1][p][q] = -inf;
for(int oo = 0; oo<2;oo++){
int nx1 = p - (oo==0);
int ny1 = i-p - (oo==1);
// cout<<nx1<<" "<<ny1<<endl;
if(!chk(nx1,ny1)) continue;
for(int uu = 0; uu<2; uu++){
int nx2 = q - (uu==0);
int ny2 = i-q - (uu==1);
// cout<<nx2<<" "<<ny2<<endl;
if(!chk(nx2,ny2)) continue;
int x1 = nx1,x2 =nx2;
if(x1>x2) swap(x1,x2);
// if(p==q) cout<<p<<" "<<i-p<<" "<<nx1<<" "<<nx2<<endl;
chkmax(dp[i&1][p][q], dp[i-1&1][x1][x2] + v);
}
}
ans = dp[i&1][p][q];
// if(p==q) cout<<"i: "<<i<<" "<<p<<" "<<q<<" "<<ans<<endl;
}
}
cout << ans << endl;
}
return 0;
}
posted on 2012-08-03 15:36
西月弦 閱讀(272)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告