1. 用贪心分别算出A单独加工n个工件的时间f1, 和B单独加工n个工件的时间f2
2. 用f1 的最小值 + f2 最大值 , 用平均贪心的思想. 再比较最大值为第二问的解.
/**//*
ID: lorelei3
TASK: job
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 1005;
const int MAXM = 35;
int t1[MAXM], t2[MAXM], w1[MAXM], w2[MAXM], f1[MAXN], f2[MAXN];
int main()
{
int i,j, n, m1, m2;
ifstream fin("job.in");
ofstream fout("job.out");
fin>>n>>m1>>m2;
for(i=1; i<=m1; ++i)
fin>>t1[i];
for(i=1; i<=m2; ++i)
fin>>t2[i];
for(i=1; i<=n; ++i){
int min=1;
for(j=2; j<=m1; ++j)
if(w1[j]+t1[j] < w1[min]+t1[min])
min=j;
w1[min] += t1[min];
f1[i] = w1[min];
min=1;
for(j=2; j<=m2; ++j)
if(w2[j]+t2[j] < w2[min]+t2[min])
min =j;
w2[min] += t2[min];
f2[i] = w2[min];
}
sort(f1+1, f1+n+1, less<int>());
sort(f2+1, f2+n+1, greater<int>());
int ans1 = f1[n], ans2 = 0;
for(i=1; i<=n; ++i)
if(f1[i]+f2[i] > ans2)
ans2 = f1[i]+f2[i];
fout<<ans1<<" "<<ans2<<endl;
return 0;
}posted @
2011-01-25 17:10 小阮 阅读(798) |
评论 (2) |
编辑 收藏
/**//*
ID: lorelei3
TASK: stall4
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int MAXN = 205;
int a[MAXN][MAXN], match[MAXN];
int n,m, ans;
bool visited[MAXN];
bool dfs(int k){
for(int i=1; i<=a[k][0]; ++i){
int v = a[k][i];
if(!visited[v]){
visited[v]=true;
if(!match[v] || dfs(match[v])){
match[v] = k;
return true;
}
}
}
return false;
}
void search(){
for(int i=1; i<=n; ++i){
memset(visited, 0, sizeof(visited));
if(dfs(i))
ans++;
}
}
int main(){
ifstream fin("stall4.in");
ofstream fout("stall4.out");
fin>>n>>m;
for(int i=1; i<=n; ++i){
fin>>a[i][0];
for(int j=1; j<=a[i][0]; ++j){
fin>>a[i][j];
}
}
search();
fout<<ans<<endl;
return 0;
}
posted @
2011-01-25 10:48 小阮 阅读(391) |
评论 (0) |
编辑 收藏
标准的最大流. 注意有重边. 重复边直接累加.
/**//*
ID: lorelei3
TASK: ditch
LANG: C++
*/
#include <fstream>
#include <queue>
#include <memory.h>
using namespace std;
const int INF = 0x7FFFFFF;
const int MAXN = 205;
int s,t,n;
long long c[MAXN][MAXN], pre[MAXN], delta[MAXN];
bool bfs(int s, int t){
int i;
queue<int> Q;
memset(pre, 0, sizeof(pre));
memset(delta, 0, sizeof(delta));
delta[s] = INF;
Q.push(s);
while(!Q.empty()){
int cur = Q.front();
Q.pop();
for(i=1; i<=n; ++i){
if(delta[i]==0 && c[cur][i]>0){
delta[i] = delta[cur]<c[cur][i] ? delta[cur] : c[cur][i];
pre[i] = cur;
Q.push(i);
}
}
}
if(delta[t]==0)
return false;
return true;
}
int edmonds_karp(int s, int t){
int i, ans=0;
while(bfs(s,t)){
for(i=t; i!=s; i=pre[i]){
c[pre[i]][i] -= delta[t];
c[i][pre[i]] += delta[t];
}
ans += delta[t];
}
return ans;
}
int main(){
int k,i,j,v;
ifstream fin("ditch.in");
ofstream fout("ditch.out");
fin>>k>>n;
s=1; t=n;
while(k--){
fin>>i>>j>>v;
c[i][j]+=v;
}
fout<<edmonds_karp(s,t)<<endl;
return 0;
}
posted @
2011-01-24 22:42 小阮 阅读(202) |
评论 (0) |
编辑 收藏
摘要: 剪枝:1. 对于任意串, 任意相邻的'C', 'O', 'W'之间的串应该在目标串中能找到.2. 通过ELFHash对串进行判重.( HASHSIZE可以大点)3. 若串的长度length 减去 目标串长度(47) MOD 3不等于0, 排除.
/**//*ID: lorelei3TASK: cryptcowLANG: C++*/#include <...
阅读全文
posted @
2011-01-24 00:25 小阮 阅读(641) |
评论 (0) |
编辑 收藏
摘要: 求一个无向图的最小环, 建立模型比较简单, 输入数据的格式比较难受, 我采用了DFS,
/**//*ID: lorelei3TASK: fence6LANG: C++*/#include <fstream>#include <memory.h>using namespace std;con...
阅读全文
posted @
2011-01-23 09:48 小阮 阅读(430) |
评论 (0) |
编辑 收藏
多维背包问题, 不能DP, 由于搜索树又宽又深, 所以可以采取DFSID.
1. 对board、rail排序。并计算sum_board。对于每个rail，小的肯定比大的容易得到，取前k个rail的和 sum_rail，
使得 sum_rail < sum_board && sum_rail + rail[k] > sum_board
2. 从大到小枚举rail时，设from数组，保存每个rail是从哪个board来的，由于rail 肯定有重复，当rail[k] == rail[k+1]时候， 第k个rail的from值肯定是大于等于第k+1个rail来自的from，最少是from[k] = from[k+1];
3.设一个浪费值waste, n个rail之和sum_rail* （区别sum_rail)， 则最多只能浪费 sum_board - sum_rail* 这么多木材，因为如果浪费更多的话，则剩余board肯定不够切
参考了USACO上边好多代码。。。
/**//*
ID: lorelei3
TASK: fence8
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
const int R = 1024;
bool flag;
int board[N], remain[N], from[N], rail[R];
int sum_board, sum_rail, max_waste, n, r,ans;
ifstream fin;
ofstream fout;
void dfs(int k, int waste){
if(k<0){
flag =true;
fout<<ans+1<<endl;
exit(0);
}else{
int i;
if(k!= ans && rail[k] == rail[k+1])
i = from[k+1];
else
i=0;
for( ; i<n; ++i)
if(remain[i]>=rail[k]){
from[k] = i;
remain[i] -= rail[k];
if(remain[i] < rail[0]) waste += remain[i];
if(waste > max_waste){
waste -= remain[i];
remain[i] += rail[k];
continue;
}
dfs(k-1, waste);
remain[i] += rail[k];
}
}
}
int main(){
flag =false;
int i, nrail;
fin.open("fence8.in");
fout.open("fence8.out");
fin>>n;
for(i=0; i<n; ++i){
fin>>board[i];
remain[i] = board[i];
sum_board += board[i];
}
fin>>r;
for(i=0; i<r; ++i)
fin>>rail[i];
sort(board, board+n);
sort(rail, rail+r);
for(i=0; i<r; ++i){
if(sum_rail+rail[i]>sum_board)
break;
sum_rail+=rail[i];
}
nrail = i;
for(i= nrail-1; i>=0; --i){
ans = i;
max_waste = sum_board - sum_rail;
sum_rail -= rail[i];
dfs(i, 0);
}
if(!flag)
fout<<0<<endl;
return 0;
}
posted @
2011-01-22 01:22 小阮 阅读(683) |
评论 (0) |
编辑 收藏可以证明结果不会超过最大的两个数的最小公倍数（如果有的话, 这部分还没做)。
判断无限解可以按上面的方法，另外也可以算所有的数的最大公约数。
如果不是1，也就是说这些数不互质，那么一定没办法构成所有的不被这个最大公约数整除的数。当且仅当这种情况会有无限解。
/**//*
ID: lorelei3
TASK: nuggets
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAX = 70000;
bool f[MAX];
int n;
int a[15];
int gcd(int a, int b){
if(b==0)
return a;
else
return gcd(b, a%b);
}
int main(){
int i,j,k;
ifstream fin("nuggets.in");
ofstream fout("nuggets.out");
fin>>n;
for(i=1; i<=n; ++i)
fin>>a[i];
k=a[1];
for(i=2; i<=n; ++i)
k = gcd(k, a[i]);
if(k!=1){
fout<<0<<endl;
return 0;
}
f[0]=true;
for(i=1; i<=n; ++i)
for(j=a[i]; j<=65536; ++j)
f[j] = f[j]||f[j-a[i]];
for(i=65536; i>=1; --i)
if(!f[i])
break;
fout<<i<<endl;
return 0;
}
posted @
2011-01-20 20:34 小阮 阅读(256) |
评论 (0) |
编辑 收藏
f[i][j][k] 从前i首歌中选, 放入前j张碟, 每张蝶时间为k 的歌曲数量.
/**//*
ID: lorelei3
TASK: rockers
LANG: C++
*/
#include <fstream>
using namespace std;
const int MAX = 25;
int f[MAX][MAX][MAX];
int cost[MAX];
int N,T,M;
inline int max(int a, int b){
return a>b? a: b;
}
int main(){
int i,j,k;
ifstream fin("rockers.in");
ofstream fout("rockers.out");
fin>>N>>T>>M;
for(i=1; i<=N; ++i)
fin>>cost[i];
for(i=1; i<=N; ++i)
for(j=1; j<=M; ++j)
for(k=1; k<=T; ++k)
if(k<cost[i])
f[i][j][k] = max(f[i-1][j][k], f[i-1][j-1][T]); // 如果不选, 就取要这k分钟+以前的专辑的最优值 或 以前的专辑的最优值
else
f[i][j][k] = max(f[i-1][j][k-cost[i]], f[i-1][j-1][T])+1; //取这首歌 取以前专辑的最优值+1 或 取当前专辑的最优值+1
fout<<f[N][M][T]<<endl;
return 0;
}
posted @
2011-01-20 17:22 小阮 阅读(414) |
评论 (0) |
编辑 收藏皮克定理说明了其面积S和内部格点数目a、边上格点数目b的关系：S = a + b/2 - 1。
根据三角形面积公式求出S。
如果知道了b，那么三角形内部格点数目a也就求出来了。
可以证明，一条直线((0,0),(n,m))上的格点数等于n与m的最大公约数+1。即b=gcd(n,m)+1. gcd(n,m)为n与m的最大公约数。
/**//*
ID: lorelei3
TASK: fence9
LANG: C++
*/
#include <fstream>
#include <cmath>
#include <iostream>
using namespace std;
int m,n,p;
int gcd(int a, int b){
if(b==0) return a;
else return gcd(b, a%b);
}
int main(){
int S, a, b=0;
ifstream fin("fence9.in");
ofstream fout("fence9.out");
fin>>n>>m>>p;
b += gcd(n,m);
b += gcd(abs(n-p),m);
b += p;
S = (p*m)/2;
//S = a + b/2 - 1;
a = S+1-b/2;
fout<<a<<endl;
return 0;
}
代入皮克公式，即可求出a的值
posted @
2011-01-19 19:04 小阮 阅读(237) |
评论 (0) |
编辑 收藏
采取递归的方法建立二叉树。
首先取前序遍历的首元素当作二叉树的根，当前元素为根。
把前序遍历中的当前元素当作中序遍历的分割点，中序遍历分割点前面的元素一定在当前元素的左子树，分割点后面元素一定在当前元素的右子树。然后加入下一个顶点，再把它当作分割点。
如此递归的进行，直到二叉树建立完成。
/**//*
ID: lorelei3
TASK: heritage
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <memory.h>
#include <string.h>
using namespace std;
const int MAX = 100;
const int N = 10000;
int t;
char pre[MAX], mid[MAX], tree[N];
ifstream fin;
ofstream fout;
void Build(int n, char* pre, char* mid, int i){
if(n<=0)
return;
tree[i] = pre[0];
int p = strchr(mid, pre[0]) - mid;
Build(p, pre+1, mid, 2*i);
Build(n-p-1, pre+p+1, mid+p+1, 2*i+1);
}
void PostOrder(int i){
if(tree[i]==NULL)
return;
PostOrder(2*i);
PostOrder(2*i+1);
fout<<tree[i];
}
int main(){
fin.open("heritage.in");
fout.open("heritage.out");
memset(tree, NULL, sizeof(tree));
fin>>mid>>pre;
Build(strlen(pre), pre, mid, 1);
PostOrder(1);
fout<<endl;
return 0;
}
posted @
2011-01-19 16:39 小阮 阅读(197) |
评论 (0) |
编辑 收藏