AcWing 307. 连通图 poj1737（计数类dp，高精度）

2024-04-16 02:38
文章标签 dp 计数 acwing 连通 高精度 307 poj1737

本文主要是介绍AcWing 307. 连通图 poj1737（计数类dp，高精度），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求 N 个节点的无向连通图有多少个，节点有标号，编号为1~N。

例如下列图示，三个节点的无向连通图共4个。

1737_1.jpg

输入格式
输入包含多组测试数据。

每组数据包含一个整数N。

当输入为0时，表示输入终止。

输出格式
每组测试数据输出一个结果，每个结果占一行。

数据范围
1≤N≤50
输入样例：
1
2
3
4
0
输出样例：
1
1
4
38

思路：
f[i] = 2i*(i-1)/2 - (1≤j≤i-1)∑f[j] X C(i - 1,j - 1) X 2(i-j)X(i-j-1)/2
就是所有的情况，减去至少2个连通块的情况

本题麻烦的是高精度。高精度的问题在于慢！！打个表就好啦。

ACnew

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;const int maxn = 1000;struct bign{int d[maxn], len;void clean() { while(len > 1 && !d[len-1]) len--; }bign() 			{ memset(d, 0, sizeof(d)); len = 1; }bign(int num) 	{ *this = num; } bign(char* num) { *this = num; }bign operator = (const char* num){memset(d, 0, sizeof(d)); len = strlen(num);for(int i = 0; i < len; i++) d[i] = num[len-1-i] - '0';clean();return *this;}bign operator = (int num){char s[20]; sprintf(s, "%d", num);*this = s;return *this;}bign operator + (const bign& b){bign c = *this; int i;for (i = 0; i < b.len; i++){c.d[i] += b.d[i];if (c.d[i] > 9) c.d[i]%=10, c.d[i+1]++;}while (c.d[i] > 9) c.d[i++]%=10, c.d[i]++;c.len = max(len, b.len);if (c.d[i] && c.len <= i) c.len = i+1;return c;}bign operator - (const bign& b){bign c = *this; int i;for (i = 0; i < b.len; i++){c.d[i] -= b.d[i];if (c.d[i] < 0) c.d[i]+=10, c.d[i+1]--;}while (c.d[i] < 0) c.d[i++]+=10, c.d[i]--;c.clean();return c;}bign operator * (const bign& b)const{int i, j; bign c; c.len = len + b.len; for(j = 0; j < b.len; j++) for(i = 0; i < len; i++) c.d[i+j] += d[i] * b.d[j];for(i = 0; i < c.len-1; i++)c.d[i+1] += c.d[i]/10, c.d[i] %= 10;c.clean();return c;}bign operator / (const bign& b){int i, j;bign c = *this, a = 0;for (i = len - 1; i >= 0; i--){a = a*10 + d[i];for (j = 0; j < 10; j++) if (a < b*(j+1)) break;c.d[i] = j;a = a - b*j;}c.clean();return c;}bign operator % (const bign& b){int i, j;bign a = 0;for (i = len - 1; i >= 0; i--){a = a*10 + d[i];for (j = 0; j < 10; j++) if (a < b*(j+1)) break;a = a - b*j;}return a;}bign operator += (const bign& b){*this = *this + b;return *this;}bool operator <(const bign& b) const{if(len != b.len) return len < b.len;for(int i = len-1; i >= 0; i--)if(d[i] != b.d[i]) return d[i] < b.d[i];return false;}bool operator >(const bign& b) const{return b < *this;}bool operator<=(const bign& b) const{return !(b < *this);}bool operator>=(const bign& b) const{return !(*this < b);}bool operator!=(const bign& b) const{return b < *this || *this < b;}bool operator==(const bign& b) const{return !(b < *this) && !(b > *this);}string str() const{char s[maxn]={};for(int i = 0; i < len; i++) s[len-1-i] = d[i]+'0';return s;}
};istream& operator >> (istream& in, bign& x)
{string s;in >> s;x = s.c_str();return in;
}ostream& operator << (ostream& out, const bign& x)
{out << x.str();return out;
}bign c[55][55];void ready()
{for(int i=0;i<=50;i++)c[i][0]=1;for(int i=1;i<=50;i++){for(int j=1;j<=i;j++){c[i][j]=c[i-1][j-1]+c[i-1][j];}}
}bign d[100],g[100],h[100],t,two;void init()
{ready();d[1]=1;g[1]=0;h[1]=1;t = 1;two = 2;for(int i=2;i<=50;i++){for(int j=1;j<=i-1;j++){g[i]=(g[i]+(c[i - 1][j - 1]*d[j])*h[i-j]);}t=two*t;h[i]=t*h[i-1];d[i]=h[i]-g[i];}
}int main()
{ios::sync_with_stdio(false);init();int n;while(cin >> n && n)cout << d[n] << endl;
}


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;#pragma GCC optimize(2)
typedef long long ll;
class DividedByZeroException {};class BigInteger {
private:vector<char> digits;bool sign;          //  true for positive, false for negitivevoid trim();        //  remove zeros in tail, but if the value is 0, keep only one:)
public:BigInteger(int);    // construct with a int integerBigInteger(string&) ;BigInteger();BigInteger(const BigInteger&);BigInteger operator=(const BigInteger& op2);BigInteger    abs() const;BigInteger    pow(int a);//binary operatorsfriend BigInteger operator+=(BigInteger&, const BigInteger&);friend BigInteger operator-=(BigInteger&, const BigInteger&);friend BigInteger operator*=(BigInteger&, const BigInteger&);friend BigInteger operator/=(BigInteger&, const BigInteger&) throw(DividedByZeroException);friend BigInteger operator%=(BigInteger&, const BigInteger&) throw(DividedByZeroException);friend BigInteger operator+(const BigInteger&, const BigInteger&);friend BigInteger operator-(const BigInteger&, const BigInteger&);friend BigInteger operator*(const BigInteger&, const BigInteger&);friend BigInteger operator/(const BigInteger&, const BigInteger&) throw(DividedByZeroException);friend BigInteger operator%(const BigInteger&, const BigInteger&) throw(DividedByZeroException);//uniary operatorsfriend BigInteger operator-(const BigInteger&);   //negativefriend BigInteger operator++(BigInteger&);        //++vfriend BigInteger operator++(BigInteger&, int);   //v++friend BigInteger operator--(BigInteger&);        //--vfriend BigInteger operator--(BigInteger&, int);   //v--friend bool operator>(const BigInteger&, const BigInteger&);friend bool operator<(const BigInteger&, const BigInteger&);friend bool operator==(const BigInteger&, const BigInteger&);friend bool operator!=(const BigInteger&, const BigInteger&);friend bool operator>=(const BigInteger&, const BigInteger&);friend bool operator<=(const BigInteger&, const BigInteger&);friend ostream& operator<<(ostream&, const BigInteger&);   //print the BigIntegerfriend istream& operator>>(istream&, BigInteger&);         // input the BigIntegerpublic:static const BigInteger ZERO;static const BigInteger ONE;static const BigInteger TEN;
};
const BigInteger BigInteger::ZERO = BigInteger(0);
const BigInteger BigInteger::ONE = BigInteger(1);
const BigInteger BigInteger::TEN = BigInteger(10);BigInteger::BigInteger() {sign = true;
}BigInteger::BigInteger(int val) { // construct with a int integerif (val >= 0) {sign = true;}else {sign = false;val *= (-1);}do {digits.push_back((char)(val % 10));val /= 10;} while (val != 0);
}BigInteger::BigInteger(string& def) {sign = true;for (string::reverse_iterator iter = def.rbegin() ; iter < def.rend();  iter++) {char ch = (*iter);if (iter == def.rend() - 1) {if (ch == '+') {break;}if (ch == '-') {sign = false;break;}}digits.push_back((char)((*iter) - '0'));}trim();
}void BigInteger::trim() {vector<char>::reverse_iterator iter = digits.rbegin();while (!digits.empty() && (*iter) == 0) {digits.pop_back();iter = digits.rbegin();}if (digits.size() == 0) {sign = true;digits.push_back(0);}
}BigInteger::BigInteger(const BigInteger& op2) {sign = op2.sign;digits = op2.digits;
}BigInteger BigInteger::operator=(const BigInteger& op2) {digits = op2.digits;sign = op2.sign;return (*this);
}BigInteger BigInteger::abs() const {if (sign) {return *this;}else {return -(*this);}
}BigInteger BigInteger::pow(int a) {BigInteger res(1);for (int i = 0; i < a; i++) {res *= (*this);}return res;
}//binary operators
BigInteger operator+=(BigInteger& op1, const BigInteger& op2) {if (op1.sign == op2.sign) {     //只处理相同的符号的情况，异号的情况给-处理vector<char>::iterator iter1;vector<char>::const_iterator iter2;iter1 = op1.digits.begin();iter2 = op2.digits.begin();char to_add = 0;        //进位while (iter1 != op1.digits.end() && iter2 != op2.digits.end()) {(*iter1) = (*iter1) + (*iter2) + to_add;to_add = ((*iter1) > 9);    // 大于9进一位(*iter1) = (*iter1) % 10;iter1++;iter2++;}while (iter1 != op1.digits.end()) {    //(*iter1) = (*iter1) + to_add;to_add = ((*iter1) > 9);(*iter1) %= 10;iter1++;}while (iter2 != op2.digits.end()) {char val = (*iter2) + to_add;to_add = (val > 9) ;val %= 10;op1.digits.push_back(val);iter2++;}if (to_add != 0) {op1.digits.push_back(to_add);}return op1;}else {if (op1.sign) {return op1 -= (-op2);}else {return op1 = op2 - (-op1);}}}BigInteger operator-=(BigInteger& op1, const BigInteger& op2) {if (op1.sign == op2.sign) {     //只处理相同的符号的情况，异号的情况给+处理if (op1.sign) {if (op1 < op2) { // 2 - 3return  op1 = -(op2 - op1);}}else {if (-op1 > -op2) { // (-3)-(-2) = -(3 - 2)return op1 = -((-op1) - (-op2));}else {           // (-2)-(-3) = 3 - 2return op1 = (-op2) - (-op1);}}vector<char>::iterator iter1;vector<char>::const_iterator iter2;iter1 = op1.digits.begin();iter2 = op2.digits.begin();char to_substract = 0;  //借位while (iter1 != op1.digits.end() && iter2 != op2.digits.end()) {(*iter1) = (*iter1) - (*iter2) - to_substract;to_substract = 0;if ((*iter1) < 0) {to_substract = 1;(*iter1) += 10;}iter1++;iter2++;}while (iter1 != op1.digits.end()) {(*iter1) = (*iter1) - to_substract;to_substract = 0;if ((*iter1) < 0) {to_substract = 1;(*iter1) += 10;}else {break;}iter1++;}op1.trim();return op1;}else {if (op1 > BigInteger::ZERO) {return op1 += (-op2);}else {return op1 = -(op2 + (-op1));}}
}
BigInteger operator*=(BigInteger& op1, const BigInteger& op2) {BigInteger result(0);if (op1 == BigInteger::ZERO || op2 == BigInteger::ZERO) {result = BigInteger::ZERO;}else {vector<char>::const_iterator iter2 = op2.digits.begin();while (iter2 != op2.digits.end()) {if (*iter2 != 0) {deque<char> temp(op1.digits.begin(), op1.digits.end());char to_add = 0;deque<char>::iterator iter1 = temp.begin();while (iter1 != temp.end()) {(*iter1) *= (*iter2);(*iter1) += to_add;to_add = (*iter1) / 10;(*iter1) %= 10;iter1++;}if (to_add != 0) {temp.push_back(to_add);}int num_of_zeros = iter2 - op2.digits.begin();while (num_of_zeros--) {temp.push_front(0);}BigInteger temp2;temp2.digits.insert(temp2.digits.end(), temp.begin(), temp.end());temp2.trim();result = result + temp2;}iter2++;}result.sign = ((op1.sign && op2.sign) || (!op1.sign && !op2.sign));}op1 = result;return op1;
}BigInteger operator/=(BigInteger& op1, const BigInteger& op2) throw(DividedByZeroException) {if (op2 == BigInteger::ZERO) {throw DividedByZeroException();}BigInteger t1 = op1.abs(), t2 = op2.abs();if (t1 < t2) {op1 = BigInteger::ZERO;return op1;}//现在 t1 > t2 > 0//只需将 t1/t2的结果交给result就可以了deque<char> temp;vector<char>::reverse_iterator iter = t1.digits.rbegin();BigInteger temp2(0);while (iter != t1.digits.rend()) {temp2 = temp2 * BigInteger::TEN + BigInteger((int)(*iter));char s = 0;while (temp2 >= t2) {temp2 = temp2 - t2;s = s + 1;}temp.push_front(s);iter++;}op1.digits.clear();op1.digits.insert(op1.digits.end(), temp.begin(), temp.end());op1.trim();op1.sign = ((op1.sign && op2.sign) || (!op1.sign && !op2.sign));return op1;
}BigInteger operator%=(BigInteger& op1, const BigInteger& op2) throw(DividedByZeroException) {return op1 -= ((op1 / op2) * op2);
}BigInteger operator+(const BigInteger& op1, const BigInteger& op2) {BigInteger temp(op1);temp += op2;return temp;
}
BigInteger operator-(const BigInteger& op1, const BigInteger& op2) {BigInteger temp(op1);temp -= op2;return temp;
}BigInteger operator*(const BigInteger& op1, const BigInteger& op2) {BigInteger temp(op1);temp *= op2;return temp;}BigInteger operator/(const BigInteger& op1, const BigInteger& op2) throw(DividedByZeroException) {BigInteger temp(op1);temp /= op2;return temp;
}BigInteger operator%(const BigInteger& op1, const BigInteger& op2) throw(DividedByZeroException) {BigInteger temp(op1);temp %= op2;return temp;
}//uniary operators
BigInteger operator-(const BigInteger& op) {  //negativeBigInteger temp = BigInteger(op);temp.sign = !temp.sign;return temp;
}BigInteger operator++(BigInteger& op) {   //++vop += BigInteger::ONE;return op;
}BigInteger operator++(BigInteger& op, int x) { //v++BigInteger temp(op);++op;return temp;
}BigInteger operator--(BigInteger& op) {   //--vop -=  BigInteger::ONE;return op;
}BigInteger operator--(BigInteger& op, int x) { //v--BigInteger temp(op);--op;return temp;
}bool operator<(const BigInteger& op1, const BigInteger& op2) {if (op1.sign != op2.sign) {return !op1.sign;}else {if (op1.digits.size() != op2.digits.size())return (op1.sign && op1.digits.size() < op2.digits.size())|| (!op1.sign && op1.digits.size() > op2.digits.size());vector<char>::const_reverse_iterator iter1, iter2;iter1 = op1.digits.rbegin();iter2 = op2.digits.rbegin();while (iter1 != op1.digits.rend()) {if (op1.sign &&  *iter1 < *iter2) {return true;}if (op1.sign &&  *iter1 > *iter2) {return false;}if (!op1.sign &&  *iter1 > *iter2) {return true;}if (!op1.sign &&  *iter1 < *iter2) {return false;}iter1++;iter2++;}return false;}
}
bool operator==(const BigInteger& op1, const BigInteger& op2) {if (op1.sign != op2.sign  || op1.digits.size() != op2.digits.size()) {return false;}vector<char>::const_iterator iter1, iter2;iter1 = op1.digits.begin();iter2 = op2.digits.begin();while (iter1 != op1.digits.end()) {if (*iter1 != *iter2) {return false;}iter1++;iter2++;}return true;
}bool operator!=(const BigInteger& op1, const BigInteger& op2) {return !(op1 == op2);
}bool operator>=(const BigInteger& op1, const BigInteger& op2) {return (op1 > op2) || (op1 == op2);
}bool operator<=(const BigInteger& op1, const BigInteger& op2) {return (op1 < op2) || (op1 == op2);
}bool operator>(const BigInteger& op1, const BigInteger& op2) {return !(op1 <= op2);
}ostream& operator<<(ostream& stream, const BigInteger& val) {  //print the BigIntegerif (!val.sign) {stream << "-";}for (vector<char>::const_reverse_iterator iter = val.digits.rbegin(); iter != val.digits.rend() ; iter++) {stream << (char)((*iter) + '0');}return stream;
}istream& operator>>(istream& stream, BigInteger& val) {   //Input the BigIntegerstring str;stream >> str;val = BigInteger(str);return stream;
}//int main() {
//    BigInteger A;
//    int B;
//    BigInteger C = 888;
//    cin >>B;
//    cout << "A-B:" << A - B << endl;
//    cout << "A+B:" << A + B << endl;
//    cout << "A*B:" << A*B << endl;
//    cout << "A/B:" << A / B << endl;
//    cout << "A%B:" << A % B << endl;
//    cout <<  A.pow(B-3) << endl;
//    A++;
//    cout << "A++:" << A << endl;
//    A--;
//    cout << "A--:" << A << endl;
//    cout << "++B:" << ++B << endl;
//    cout << "--B:" << --B << endl;
//    cout << "C:" << C << endl;
//}BigInteger c[55][55];void ready()
{for(int i=0;i<=50;i++)c[i][0]=1;for(int i=1;i<=50;i++){for(int j=1;j<=i;j++){c[i][j]=c[i-1][j-1]+c[i-1][j];}}
}BigInteger d[100],g[100],h[100],t;void init()
{ready();d[1]=1;g[1]=0;h[1]=1;t = 1;for(int i=2;i<=50;i++){for(int j=1;j<=i-1;j++){g[i]=(g[i]+(c[i - 1][j - 1]*d[j])*h[i-j]);}t=2*t;h[i]=t*h[i-1];d[i]=h[i]-g[i];}
}string ans[100] =
{"1","1","4","38","728","26704","1866256","251548592","66296291072","34496488594816","35641657548953344","73354596206766622208","301272202649664088951808","2471648811030443735290891264","40527680937730480234609755344896","1328578958335783201008338986845427712","87089689052447182841791388989051400978432","11416413520434522308788674285713247919244640256","2992938411601818037370034280152893935458466172698624","1569215570739406346256547210377768575765884983264804405248","1645471602537064877722485517800176164374001516327306287561310208","3450836972295011606260171491426093685143754611532806996347023345844224","14473931784581530777452916362195345689326195578125463551466449404195748970496","121416458387840348322477378286414146687038407628418077332783529218671227143860518912","2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472","68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896","4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344","615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208","165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128","88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584","95268202520385449790227094691687836722278710954949736428196756305746453532341035148366531266372862653739009088659598082113309304400438624256","204586909944926298207861553173799965921067126517774603507480126827588404754232387878919170016875623577048105576068684204467114231315623298308706926592","878694093745349914731889727208157807680003171098920968952145189548012830636076748530741378813207711246134152874638123892704663922045456803250047261786444398592","7547924819767483287594694542205326068855891655862820018679189530528628155893698967796630219069788201405972928386025644172169109953194652176102437455457970998547197198336","129672361263353660216004848405397154497075914498088480263529787446798464815868889966259599220355751574955667311875199310825316757090836792227021420332597263591744872066219249762304","4455508410978470003213152055317479855991723332650114280703483486331017198541367912550307040027205813596014620050254013798901452927850711294962075802234712748298505435020109941966616435621888","306180206751230090930313674296749763317292930219833760674864513181351793147422958983304199997791891477494238067606067864147691875149221011750587805454462256284237767964756224079011437145490032917741568","42081087200752140195116730773102052524009718837902621183664949269856744858385083976643391056195246283737633254986683196506525739229100562028667655727478159896469450443625002559600024194689577683162985133342982144","11567161173227696466220457283329529101751379197153495724502457893891478829937149071434453800538222228465001645119757350054456753856800058471020811256328606811309950183460999195585736337722940242137574318489684508433109221376","6359114105601017351375465630036218352726964545083913061809864302427743340641476112983635151514041188995967358659226381513838435962182371853731281705837980150384424607870600516842502175922529566100381861494213531965265765000213275082752","6991919901710702396948942815573257427744311018004588489866790612959056357721564695830748688904669995738081555372234543689358610668809196548322563461899302515136978058611651369187392760821440875968116963440793130046454847480988052748303630065467392","15375394465098365435098131065240195173750887603455691084898736566282027607324662718653380384318359771738669872579070523864682029424324656980343742654131923883848453279046887366030428581980234722002609397042921130626427482776226373410811403774539364168814821376","67621699984704009571087635348261788647460730411971168452281282746962798999895717916292043207408657855232972628889146834646084600650980317820241001687549180689983916950502853108787655643356237905731863505593837387547463783553663104052737827256888296815897621036524900450304","594806763388137870319868932592503661181879874998563369872608575294390559331829154567126246824792929668641338543467328561106071308881273503814138669414317911219402066314092130747535752627679688399993515689603622744525243838714230998285264232171322066511990049433899384262102238508351488","10463951242026625501784363274596214619943325701401522513836100192928357652762255136769619473700702276949844553770347735730521468871772581157963359677917896206658361141741863952608795675733168160935829452838892433190712974942475048711118429563334205007874224852816312589287727030417085994911901155328","368167554019320956145827247050509963076959450983143444578072117098399777382502455552633802915095691807005512740224345254318634273382517137823997743877511866703540358482988273801636313118482363728678083259725882776454656507629131210255280738244476783496709369751571318821222548711309212127848471930415455355797504","25907488423318455274080473672019976083009208996271003791416218114322853582878049179546761491016196610119349803222490393175612695149120594742502991139032865749979736985340247224801444473477196529096332604358326020598992443433363048888842556850935198901353471923472154386768107635993449205071378228596636214817388982756553261056","3646154850293767810262810894999553363628589110640769385457986485984919161321600546344826908488589572223649058216506920510786720770519258252897810249930214560211056122090333850686659187132094273815095247787669459869137017783625755540375408272361426098383313551230976557640520636974573279383371834513917048967432546435999569365350430111956992","1026301351570055077911628972867042177680735585635225345203536190737910863123857244548313982876228994987864700400759811456244128889754306386459557887432298148719591734971030611474690885904247396313959818854940592795291449937598794070517570167551607950979266237997797283563645242105244737520881371410960067902176629829514256225641238164014573644333472284672","577756298062641319815321284633539861082132919998722885657507672188606317696301924134068233518707877841769252356274834883678320922291785288952259324960085933885572481476441044041666245632947630667669900623389069655523344952222114179660086674251300523449279256078271770682664276058349275922600493471476178420154378012048571333436567365397136152469165480980158369042006016"};
int main()
{ios::sync_with_stdio(false);
//    init();int n;
//    for(int i = 1;i <= 50;i++)
//    {
//        cout << "\"" <<  d[i] << "\"," << endl;
//        cout << endl;
//    }while(cin >> n && n)cout << ans[n - 1] << endl;
}

这篇关于AcWing 307. 连通图 poj1737（计数类dp，高精度）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/907603。

相关文章

hdu4826（三维DP）

hdu4826（三维DP）

这是一个百度之星的资格赛第四题 题目链接：http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意：从左上角的点到右上角的点，每个点只能走一遍，走的方向有三个：向上，向下，向右，求最大值。 咋一看像搜索题，先暴搜，TLE,然后剪枝，还是TLE.然后我就改方法，用DP来做，这题和普通dp相比，多个个向上
阅读更多...
hdu1011（背包树形DP）

hdu1011（背包树形DP）

没有完全理解这题， m个人，攻打一个map，map的入口是1，在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu4865(概率DP)

hdu4865(概率DP)

题意：已知前一天和今天的天气概率，某天的天气概率和叶子的潮湿程度的概率，n天叶子的湿度，求n天最有可能的天气情况。 思路：概率DP，dp[i][j]表示第i天天气为j的概率，状态转移如下：dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下： #include <stdio.h>#include
阅读更多...
usaco 1.1 Broken Necklace（DP）

usaco 1.1 Broken Necklace（DP）

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于： 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b
阅读更多...
uva 10154 DP 叠乌龟

uva 10154 DP 叠乌龟

题意： 给你几只乌龟，每只乌龟有自身的重量和力量。 每只乌龟的力量可以承受自身体重和在其上的几只乌龟的体重和内。 问最多能叠放几只乌龟。 解析： 先将乌龟按力量从小到大排列。 然后dp的时候从前往后叠，状态转移方程： dp[i][j] = dp[i - 1][j];if (dp[i - 1][j - 1] != inf && dp[i - 1][j - 1] <= t[i]
阅读更多...
uva 10118 dP

uva 10118 dP

题意： 给4列篮子，每次从某一列开始无放回拿蜡烛放入篮子里，并且篮子最多只能放5支蜡烛，数字代表蜡烛的颜色。 当拿出当前颜色的蜡烛在篮子里存在时，猪脚可以把蜡烛带回家。 问最多拿多少只蜡烛。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cs
阅读更多...
uva 10069 DP + 大数加法

uva 10069 DP + 大数加法

代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <queue>#include <map>#include <cl
阅读更多...
uva 10029 HASH + DP

uva 10029 HASH + DP

题意： 给一个字典，里面有好多单词。单词可以由增加、删除、变换，变成另一个单词，问能变换的最长单词长度。 解析： HASH+dp 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
阅读更多...
XTU 1233 n个硬币连续m个正面个数（dp）

XTU 1233 n个硬币连续m个正面个数（dp）

题面： Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2