POJ3181 Dollar Dayz(DP)

题意：

将N分解为为1~K的因子，求有几种分解方法。

要点：

这题挺难，用dp[n][m]表示n分解后最大因子为m的分解方法总和。可以写出状态转移方程dp[i][j]=dp[i][j-1]+dp[i-j][j-1]+……，可以这么理解：dp[i][j]可以由最大因子为j-1的通过i减去j的整数倍来得到。还可以进一步优化，这题还要用到大数的加法，用两个数组分别存储低位和高位可以做到，但是我觉得这么做有点问题，如果低位加起来正好出现前导0就会出现错误，这题可能数据比较水吧。

参考博客：点击打开链接 点击打开链接

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define inf 100000000000000000 
//long long是9.22..*10^18次方,保证两个相加一定不超过long long dp[1005][105][2];//0高位，1低位int main()
{int n, m,i,j;while (scanf("%d%d", &n, &m) != EOF){memset(dp, 0, sizeof(dp));for (i = 0; i <= m; i++)dp[0][i][1] = 1;//达到总和为0的都是1（什么都不需要一种）for(i=1;i<=n;i++)for (j = 1; j <= m; j++){if (i < j)//n比m小的情况,dp[n][m]=dp[n][n],一直前推{dp[i][j][0] = dp[i][j-1][0];dp[i][j][1] = dp[i][j-1][1];}else{dp[i][j][0] = dp[i][j - 1][0] + dp[i - j][j][0];dp[i][j][1] = dp[i][j - 1][1] + dp[i - j][j][1];dp[i][j][0] += dp[i][j][1] / inf;dp[i][j][1] = dp[i][j][1] % inf;}}if (dp[n][m][0])printf("%lld", dp[n][m][0]);printf("%lld\n", dp[n][m][1]);}return 0;
}