SRM 585 DIV 1 요약

제목: H 높이의 완전 두 갈래 나무 길을 줄게. 적어도 몇 대의 차가 이 길을 다 가면 차가 돌아올 수 없냐고 물어봐.
그렇다면 가장 좋은 방안은 어릴 때부터 위층으로 걸어가면 쉽게 일종의 추이를 얻을 수 있다는 것이다. 주의해야 할 것은 dp[0]=1
 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>



using namespace std;



class TrafficCongestion {

public:

	int theMinCars(int);

};

#define LL long long

const int mod = 1000000007;

LL dp[1000005];

int TrafficCongestion::theMinCars(int n) {

	dp[0] = 1;

	dp[1] = 1;

	LL pre = 2;

	for(int i = 2;i <= n; i++) {

		dp[i] = dp[i-2] + pre;

		dp[i] %= mod;

		pre = pre*2%mod;

	}

	return dp[n];

}

 
0에서 n-1까지의 숫자의 수량을 드리겠습니다. k개의 엄격하게 증가하는 서열을 구성할 수 있는 방안이 몇 가지가 있느냐고 물었더니 결과적으로mod에 대한 여유를 얻었습니다.
그러면 우리는 dp[i][j]로 전 i종의 숫자를 넣고 j개의 엄격하게 증가하는 서열을 구성하는 종수를 나타낸다. 다음에 i+1개의 숫자를 넣는다. 여기서 cnt는 전 i개의 숫자를 대표하고cur는 i+1의 개수를 나타낸다. j개의 서열에 대해 L개의 i+1을 뒤에 놓아야 한다. 나머지 i+1은 cnt-j+1이고 나머지 i+1의 개수는cur-L이다.우리는 cnt-j+1을 a,cur-L을 b로 간소화했다.
문제는 a곳에 b개의 물건을 넣는 방안수로 바뀌었다. 어떤 곳은 물건을 놓지 않을 수 있다. 그러면 우리는 인위적으로 a개의 물건을 추가했다. 지금은 a+b개의 물건이 있다. a-1의 칸막이로 a+b개의 물건을 a분으로 나눌 수 있다. 각 칸막이에는 적어도 1개의 물건이 있고 선택할 수 있는 칸막이가 a+b-1개가 있다.이것은 a곳에 b개의 물건을 놓고 어떤 곳은 물건을 놓지 않아도 된다는 것과 같다!고전적인 칸막이법!
 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <ctime>

#define LL long long



using namespace std;



class LISNumber {

public:

	int count(vector <int>, int);

};



LL c[1505][1505], dp[38][1505];

const int mod = 1000000007;

int LISNumber::count(vector <int> card, int K) {

	int i, j, l;

	c[0][0] = 1;

	for(i = 1;i <= 1500; i++) {

		c[i][0] = 1;

		for(j = 1;j <= i; j++)

			c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod;

	}

	memset(dp, 0, sizeof(dp));

	dp[0][card[0]] = 1;

	int cnt = card[0];

	for(i = 1;i < card.size(); i++) {

		int cur = card[i];

		for(j = 1;j <= K; j++) {

			if(!dp[i-1][j])	continue;

			for(l = 0;l <= j; l++)	if(cur + j - l <= K && cur >= l)

				dp[i][cur-l+j] = (dp[i][cur-l+j] + dp[i-1][j]%mod*c[j][l]%mod*c[cnt+cur-j][cur-l])%mod ;

		}

		cnt += cur;

	}

	return dp[card.size()-1][K];

}