程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SRM 612 D2L3:PowersOfTwo.htm,dp

SRM 612 D2L3:PowersOfTwo.htm,dp

編輯:C++入門知識

 

代碼:

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define CHECKTIME() printf(%.2lf
, (double)clock() / CLOCKS_PER_SEC)
typedef pair pii;
typedef long long llong;
typedef pair pll;
#define mkp make_pair

/*************** Program Begin **********************/
long long dp[65][55];
vector  X(60);
class PowersOfTwo {
public:
	long long rec(int k, int b)
	{
		long long & res = dp[k][b];
		if (res != -1) {
			return res;
		}
		// base case
		if (k == X.size()) {
			res = 1;
			return res;
		}
		res = 0;
		int x_k = X[k] + b;
		res += rec(k + 1, x_k / 2);
		if (x_k > 0) {
			res += rec(k + 1, (x_k - 1) / 2);
		}

		return res;
	}
	long long count(vector  powers) {
		long long res = 0LL;
		memset(dp, -1, sizeof(dp));
		for (int i = 0; i < X.size(); i++) {
			X[i] = std::count(powers.begin(), powers.end(), 1LL << i);
		}
		res = rec(0, 0);
		return res;
	}

};

/************** Program End ************************/


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved