Dollar Dayz poj3181

http://poj.org/problem?id=3181

这个题目一开始就能看出来是个ｄｐ问题，但是我并没有一开始就看出来是一个完全背包为题，只是想着根据以前的方法，这个问题应该是可以找到规律的，但是，还是被坑了，这还是一个大数问题！

首先我膜拜一下hankcs大神的：

///////////////////////////////////////////////////////////

#include <iostream>
using namespace std;
unsigned long long dp[100 + 16][1000 + 16]; // dp[i][j] := 用i种价格配出金额j的方案数
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int N, K;
cin >> N >> K;
dp[0][0] = 1;
for (int i = 1; i <= K; ++i)
{
for (int k = 0; k <= N; k += i)
{
for (int j = N; j >= k; --j)
{
dp[i][j] += dp[i - 1][j - k];
}
}
}
cout << dp[K][N] << endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
return 0;
}
////////////////////////////////////////////////////////////

　　hancks的这个做法是用完全背包

　　dp[i][j] = dp[i – 1][j] + dp[i – 1][j – i] + dp[i – 1][j – 2 * i] + … + dp[i – 1][0]

　　由这个公式可以再递推：　　

将j换成j – i有

dp[i][j – i] = dp[i – 1][j – i] + dp[i – 1][j – 2 * i] + … + dp[i – 1][0]

得出:if j >= i:

　　dp[i][j] = dp[i-1][j] + dp[i][j-i];

　　我的做法是一开始就推出了这个公式，因为不小心看出了这个规律

　　　　i:1->4 ,j :1->5 dp[i][j]规律是这样的

　　　　1 1 1 1 1

　　　　1 2 2 3 3

　　　　1 2 3 4 5

　　　　1 2 3 4 6

　　　　得出了j >= i : dp[i][j] = dp[i-1][j] + dp[i][j-i]　

　　　　然而，这还是个大数问题，即使unsigned long long 都不行，开始一直没想通！

/*************************************************************************

    > File Name: DollarDayz_poj3181.cpp

    > Author: spzhao

    > Mail: spzhaol@163.com

    > Created Time: 2015年10月14日 星期三 11时13分22秒

 ************************************************************************/

#include<iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mod 10000000000000000

using namespace std;

const int N = 1005;

const int K = 105;

unsigned long long dp[100+16][1000+16][2];

int n,k;

void solve()

{

	for (int i = 1;i <= k;i++)

	{

		for (int j = 1;j <= n;j++)

		{

			if (j >= i)

			{

				dp[i][j][0] = dp[i-1][j][0]+dp[i][j-i][0];

				dp[i][j][1] = dp[i-1][j][1]+dp[i][j-i][1];

				dp[i][j][0] += dp[i][j][1]/mod;

				dp[i][j][1] = dp[i][j][1]%mod;

			}

			else

			{

				dp[i][j][0] = dp[i-1][j][0];

				dp[i][j][1] = dp[i-1][j][1];

			}

		}

	}

	if (dp[k][n][0])

		cout << dp[k][n][0];

	cout << dp[k][n][1] << endl;

}

int main ()

{

		cin >> n >> k;

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

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

		for (int i = 1;i <= k;i++)

			dp[i][0][1] = 1;

		solve();

	return 0;

}

巴特西

Dollar Dayz poj3181

最新文章

热门文章