POJ3181 Dollar Dayz
2679 ワード
前の2つの問題と同じだと思っていたのに、WAは何度か、高精度の問題を長い間考えていたので、1000 100を入力すると、1つのlong long配列でもオーバーフローし、結果は負数になります.本弱は今まだ大数の问题についてあまり研究していないので、他の大牛のブログの问题解を见て、とても利益があります~~~特にkuangbinを推荐して、详しくて、その上1歩1歩の推导があって、kuangbinのブログの点を见る価値があります私は再びkuangbinとその他の多くの大牛に感谢して、膜拝
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define maxn 1100
long long dp[maxn];
long long a[maxn];
int main()
{
int i,j;
int n,k;
long long inf=1;
for(i=0;i<18;i++)
inf*=10;
while(~scanf("%d%d",&n,&k))
{
memset(dp, 0, sizeof(dp));
memset(a, 0, sizeof(a));
dp[0]=1;
for(i=1;i<=k;i++)
{
for(j=i;j<=n;j++)
{
a[j]=(a[j-i]+a[j])+(dp[j-i]+dp[j])/inf; /* , , , */
dp[j]=(dp[j-i]+dp[j])%inf;
}
}
if(a[n])
printf("%I64d",a[n]);
printf("%I64d
",dp[n]);
}
return 0;
}