大数计算模板---zoj_3447
??????? http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4190
?
?
??????? 很多DP，贪心会涉及高精度，苦于不会JAVA和PY等，只能找了个大数计算的模板，先膜拜在学习。这个代码请参考：
?????? http://www.cppblog.com/patriking/archive/2011/01/09/138137.html
?????? 这道题贪心。结果最大的策略就是：不断最小的两个数，计算后放回数集之中；相反的，结果最小的策略就是：不断取出K个（如果不足则取出全部）最大的数，计算后放回数集之中。题目结果很大，需要高精度。
???????
#include<stdio.h>#include<algorithm>#include<vector>#include<iterator>#include<string.h>using namespace std;const int MAXN = 102;class bigInt{ public: int num[302], len; bigInt() { num[0] = 0, len = 0; } bigInt operator=(const int &a) { int tmp = a; len = 0; while (tmp) num[len++] = tmp % 10, tmp /= 10; if (!len) num[0] = 0, len = 1; } bigInt(const int &a) { int tmp = a; len = 0; while (tmp) num[len++] = tmp % 10, tmp /= 10; if (!len) num[0] = 0, len = 1; } bool operator<(const bigInt &a) { if (a.len != len) return len < a.len; for (int i = len - 1; i >= 0; i--) if (num[i] != a.num[i]) return num[i] < a.num[i]; return false; } bigInt operator+(const bigInt &a) { bigInt res; int i, j, c = 0, adda, addb; for (i = 0, j = 0; i < len || j < a.len || c; ) { adda = 0, addb = 0; if (i < len) adda = num[i++]; if (j < a.len) addb = a.num[j++]; res.num[res.len++] = (adda + addb + c) % 10; c = (adda + addb + c) / 10; } return res; } bigInt operator-(const bigInt &b) { bigInt res; int i, j, c = 0, suba, subb; for (i = 0, j = 0; i < len || j < b.len || c; ) { suba = 0, subb = 0; if (i < len) suba = num[i++]; if (j < b.len) subb = b.num[j++]; res.num[res.len++] = (suba - subb + c + 10) % 10; c = (suba - subb + c + 10) / 10 - 1; } for (i = res.len - 1; i > 0; i--) if (res.num[i]) break; res.len = i + 1; return res; } bigInt operator*(const bigInt &b) { bigInt res; int i, j, c, now, mulb, tmp; memset(res.num, 0, sizeof(int) * (len + b.len)); for (i = 0; i < len; i++) { now = i, c = 0; for (j = 0; j < b.len || c; ) { mulb = 0; if (j < b.len) mulb = b.num[j++]; tmp = res.num[now] + num[i] * mulb + c; res.num[now++] = tmp % 10; c = tmp / 10; } } for (i = len + b.len - 1; i > 0; i--) if (res.num[i]) break; res.len = i + 1; return res; } bigInt operator/(const bigInt &b) { bigInt res, diva; int i, j, c; for (i = len - 1; i >= 0; i--) { if (diva.len > 1 || diva.num[0]) { for (j = diva.len - 1; j >= 0; j--) diva.num[j + 1] = diva.num[j]; diva.len++; } diva.num[0] = num[i]; if (!diva.len) diva.len = 1; res.num[i] = 0; while (!(diva < b)) diva = diva - b, res.num[i]++; } for (i = len - 1; i > 0; i--) if (res.num[i]) break; res.len = i + 1; return res; } bigInt operator%(const bigInt &b) { bigInt res, diva; int i, j, c; for (i = len - 1; i >= 0; i--) { if (diva.len > 1 || diva.num[0]) { for (j = diva.len - 1; j >= 0; j--) diva.num[j + 1] = diva.num[j]; diva.len++; } diva.num[0] = num[i]; if (!diva.len) diva.len = 1; res.num[i] = 0; while (!(diva < b)) diva = diva - b, res.num[i]++; } for (i = diva.len - 1; i > 0; i--) if (diva.num[i]) break; diva.len = i + 1; return diva; } void display() { int i; for (i = len - 1; i > 1; i--) if (num[i]) break; for (; i >= 0; i--) printf("%d", num[i]); printf("\n"); } }; bool cmp(bigInt a, bigInt b){ return (b<a);}bool cmp1(bigInt a, bigInt b){ return (a<b);}int main(){ int x, n, k; vector<bigInt>v; vector<bigInt>t; vector<bigInt>tmp; bigInt tmpx; freopen("e:\\zoj\\zoj_3447.txt","r",stdin); while(scanf("%d%d",&n,&k)!=EOF) { v.clear(); t.clear(); for(int i = 0; i < n; i++) { scanf("%d",&x); bigInt tmp_x = x; v.push_back(tmp_x); } copy(v.begin(),v.end(),back_inserter(t)); while(v.size()>1) { tmp.clear(); sort(v.begin(),v.end(),cmp); if(v.size()> k){ for(int i = k; i < v.size(); i++){ tmp.push_back(v[i]); } tmpx = 1; for(int i = 0; i < k; i++){ tmpx = tmpx * v[i]; } tmpx = tmpx + 1; tmp.push_back(tmpx); v.swap(tmp); }else{ tmpx = 1; for(int i = 0; i < v.size(); i++) tmpx = tmpx * v[i]; tmpx = tmpx + 1; tmp.push_back(tmpx); v.swap(tmp); } } while(t.size()>1) { tmp.clear(); sort(t.begin(),t.end(),cmp1); if(t.size()>2){ for(int i = 2; i < t.size(); i++){ tmp.push_back(t[i]); } tmpx = 1; for(int i = 0; i < 2; i++){ tmpx = tmpx*t[i]; } tmpx = tmpx + 1; tmp.push_back(tmpx); t.swap(tmp); }else{ tmpx = 1; for(int i = 0; i < t.size(); i++) tmpx = tmpx * t[i]; tmpx = tmpx + 1; tmp.push_back(tmpx); t.swap(tmp); } } tmpx = t[0]-v[0]; tmpx.display(); } return 0;}?