这场只出了一道题，掉了很多分。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
西月弦 阅读(269)
评论(0) 编辑 收藏 引用 所属分类:
解题报告