首页 > 代码库 > USACO Section 2.1 Healthy Holsteins
USACO Section 2.1 Healthy Holsteins
/* ID: lucien23 PROG: holstein LANG: C++ */ #include <iostream> #include <fstream> #include <vector> using namespace std; bool compFun(int x, int y) { int temp, i = 0; while (true) { temp = 1 << i; if (temp&x > temp&y) { return true; } else if (temp&x < temp&y) { return false; } i++; } } int main() { ifstream infile("holstein.in"); ofstream outfile("holstein.out"); if(!infile || !outfile) { cout << "file operation failure!" << endl; return -1; } int arrCnt[15] = {1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767}; int V; infile >> V; int *minRequire = new int[V]; for (int i=0; i<V; i++) { infile >> minRequire[i]; } int G; infile >> G; int **feeds = new int *[G]; for (int i=0; i<G; i++) { feeds[i] = new int[V]; for (int j=0; j<V; j++) { infile >> feeds[i][j]; } } int minScoopsCnt = 16; int minScoops = 0; int *sumVita = new int[V]; int sumScoops; for (int i=1; i<=arrCnt[G-1]; i++) {//穷举遍历每一种方案 for (int k=0; k<V; k++) { sumVita[k] = 0; } sumScoops = 0; for (int j=0; j<G; j++) {//推断此方案中是否包括饲养类型j(利用移位运算) int temp = 1 << j; if ((temp & i) == temp) {//包括类型j for (int k=0; k<V; k++) { sumVita[k] += feeds[j][k]; } sumScoops++; } } int k; for (k=0; k<V; k++) { if (sumVita[k] < minRequire[k]) break; } if (k==V && (sumScoops<minScoopsCnt || (sumScoops==minScoops && compFun(minScoops, i)))) { minScoopsCnt = sumScoops; minScoops = i; } } outfile << minScoopsCnt; for (int j=0; j<G; j++) { int temp = 1 << j; if ((temp & minScoops) == temp) { outfile << " " << j+1; } } outfile << endl; return 0; }
USACO Section 2.1 Healthy Holsteins
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。