麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 學(xué)院 > 開發(fā)設(shè)計 > 正文

BZOJ 1111: [POI2007]四進制的天平Wag 進制拆分,DP求方案數(shù)

2019-11-10 19:50:51
字體:
供稿:網(wǎng)友

Description

Mary準(zhǔn)備舉辦一個聚會,她準(zhǔn)備邀請很多的人參加她的聚會。并且她準(zhǔn)備給每位來賓準(zhǔn)備一些金子作為禮物。為了不傷及每個人的臉面,每個人獲得的金子必須相同。Mary將要用一個天平來稱量出金子。她有很多的砝碼,所有砝碼的質(zhì)量都是4的冪。Mary將金子置于左邊并且將砝碼置于右盤或者兩個盤。她希望每次稱量都使用最少的砝碼。并且,他希望,每次都用不同的稱量方法稱出相同質(zhì)量的金子。對于給定的質(zhì)量n,Mary希望知道最少需要用多少個砝碼可以完成稱量,并且想知道用這么多個砝碼一共有多少種方式進行稱量。 Input

輸入文件僅包含一個整數(shù),表示Mary希望給每個人的金子的質(zhì)量。(1<=n<=10^1000) Output

輸出文件僅包含一個整數(shù),表示一共可能的稱量方式對10^9的模。 Sample Input 166

Sample Output 3

樣例解釋

一共有三種方式稱量出166。166=64+64+16+16+4+1+1。166=256-64-16-16+4+1+1。166=256-64-16-4-4-1-1。

解題方法: 我們首先考慮把 n 轉(zhuǎn)換成一個四進制數(shù)。我們記轉(zhuǎn)換完的數(shù)有 m 位,第 i 位(從低到高)的值為 num[i]。我們發(fā)現(xiàn)對于第 i 位要想滿足條件只有兩種放置方法,第一種是在天平的右盤放 num[i]個 4 i 的砝碼,第二種是在天平的右盤放 1 個 4 i+ 1 的砝碼,在天平的左盤放 4-num[i]個 4 i的砝碼。因此我們可以考慮用 DP 解決,定義狀態(tài) dp[i][j]表示第 i 到 m 位已經(jīng)處理完,dp[i][0]表示第 i 位不多放一個在右盤,dp[i][1]表示在第 i 位多放一個在右盤,最少需要放置的砝碼個數(shù)。則有: dp[i][0]=min(dp[i+1][0]+num[i],dp[i+1][1]+4-num[i]); dp[i][1]=min(dp[i+1][1]+num[i]+1,dp[i+1][1]+3-num[i]); 對于方案數(shù),只要在動態(tài)規(guī)劃的過程中順便處理一下就可以了。然后代碼參考了Po爺,蒟蒻高精度巨TM炸。。。

#include <bits/stdc++.h>using namespace std;const int maxn = 2010;const int mod = 1e9;struct bign{ int a[2010]; int len; bign() { memset(a, 0, sizeof(a)); len = 0; } inline void input() { char b[2010]; scanf("%s", b + 1); len = strlen(b + 1); for(int i = 1; i <= len; i ++) { a[i] = b[len - i + 1] - '0'; } } inline bign get_bign(int rhs) { bign ret; while(rhs) { ret.a[++ ret.len] = rhs % 10; rhs /= 10; } return ret; } inline bool Operator < (const bign& rhs) const { if(len < rhs.len) return 1; if(len > rhs.len) return 0; for(int i = len; i >= 1; i --) { if(a[i] < rhs.a[i]) return 1; if(a[i] > rhs.a[i]) return 0; } return 0; } inline bool operator > (const bign& rhs) const { return rhs < *this; } inline bool operator == (const bign& rhs) const { return !((rhs < *this) | (*this < rhs)); } inline bool operator <= (const bign& rhs) const { return *this == rhs || *this < rhs; } inline bool operator >= (const bign& rhs) const { return *this == rhs || *this > rhs; } inline bool operator != (const bign& rhs) const { return !(*this == rhs); } inline bign operator * (bign& rhs) const { bign ret; for(int i = 1; i <= len; i ++) { for(int j = 1; j <= rhs.len; j ++) { ret.a[i + j - 1] += a[i] * rhs.a[j]; ret.a[i + j] += ret.a[i + j - 1] / 10; ret.a[i + j - 1] %= 10; } } ret.len = len + rhs.len - 1; if(ret.a[ret.len + 1]) ret.len ++; return ret; } inline bign operator * (int& rhs) { bign yt = get_bign(rhs); return *this * yt; } inline bign operator + (bign& rhs) const { bign ret; ret.len = max(len, rhs.len); for(int i = 1; i <= ret.len; i ++) { ret.a[i] += a[i] + rhs.a[i]; ret.a[i + 1] += ret.a[i] / 10; ret.a[i] %= 10; } if(ret.a[ret.len + 1]) ret.len ++; return ret; } inline bign operator + (int& rhs) { bign yt = get_bign(rhs); return *this + yt; } inline bign operator - (const bign& rhs) const { bign ret; for(int i = 1; i <= len; i ++) { ret.a[i] += a[i] - rhs.a[i]; if(ret.a[i] < 0) ret.a[i] += 10, ret.a[i + 1] --; if(ret.a[i]) ret.len = i; } return ret; } inline bign operator - (int& rhs) { bign yt = get_bign(rhs); return *this - yt; } inline bign operator / (const int& rhs) const { bign ret; int x = 0; for(int i = len; i >= 1; i --) { x = x * 10 + a[i]; ret.a[i] = x / rhs; x %= rhs; } ret.len = len; while(!ret.a[ret.len] && ret.len) ret.len --; return ret; } inline int operator % (const int& rhs) const { int x = 0; for(int i = len; i >= 1; i --) { x = x * 10 + a[i]; x %= rhs; } return x; } inline bign operator ^ (int rhs) { bign ret; ret = get_bign(1); bign nbc = *this; while(rhs) { if(rhs & 1) ret = ret * nbc; nbc = nbc * nbc; rhs >>= 1; } return ret; } inline void operator = (int x) { *this = get_bign(x); return; } inline void PRint() { for(int i = len; i >= 1; i --) printf("%d", a[i]); }};int stk[maxn], top;pair <int, int> f[maxn], g[maxn];//f[i]表示從第i位往前的最小花銷及方案數(shù)//g[i]表示從第i位往前+1的最小花銷及方案數(shù)//f[i]就是dp[i][0], g[i]就是dp[i][1]void add(pair <int, int> &x, pair <int, int> y, int z){ if(y.first + z < x.first) { x.first = y.first + z, x.second = 0; } if(y.first + z == x.first) { (x.second += y.second) %= mod; }}int main(){ bign n; n.input(); while(n.len) { stk[++top] = n % 4; n = n / 4; } memset(f, 0x3f, sizeof(f)); memset(g, 0x3f, sizeof(g)); f[top + 1] = {0, 1}; g[top + 1] = {1, 1}; for(int i = top; i >= 1; i--) { if(stk[i] == 0){ add(f[i], f[i+1], 0); add(g[i], f[i+1], 1); } else if(stk[i] == 1){ add(f[i], f[i+1], 1); add(g[i], f[i+1], 2); add(g[i], g[i+1], 2); } else if(stk[i] == 2){ add(f[i], f[i+1], 2); add(f[i], g[i+1], 2); add(g[i], g[i+1], 1); } else{ add(f[i], g[i+1], 1); add(g[i], g[i+1], 0); } } cout << f[1].second << endl; return 0;}
發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表
主站蜘蛛池模板: 国产成人网 | 国产成人精品区 | 精品国产乱码久久久久久丨区2区 | 黄色一级毛片免费看 | 欧美一级黄色片免费观看 | 精品一区二区电影 | 亚州综合网 | 国产资源在线免费观看 | 一级免费特黄视频 | 精品一区二区三区不卡 | 国产男女爽爽爽爽爽免费视频 | 91社区在线观看 | 精品久久999| 亚洲一区二区中文字幕在线观看 | 色操网| 中文字幕在线播放视频 | 在线成人一区 | 中文字幕免费播放 | 午夜精品久久久久久久久久久久久蜜桃 | 国产欧美一区二区三区免费看 | www国产成人免费观看视频 | 亚洲男人的天堂在线视频 | 视频一区二区不卡 | 欧美大电影免费观看 | 色猫av | 色人阁导航 | 免费国产之a视频 | 成人男女激情免费视频 | 久久成人福利 | 久精品久久 | 欧美18—19sex性护士中国 | 黄色网址电影 | 成人午夜免费在线视频 | 日本68xxxx | 日本在线播放一区二区 | 91麻豆精品国产91久久久无需广告 | 欧美性色黄大片www 操碰网 | 久久精品性视频 | 激情在线视频 | 欧美成人精品h版在线观看 久久久久久三区 | 二区视频 |