http://acm.timus.ru/problem.aspx?space=1&num=1513
此題需要用到大整數 ? 我是用萬進制 ?輸出時要注意不要多輸出0
思路方面 可以先想出來二維的解法 ?然后發現二維的可以轉化為一維的 ?
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#define LL long long
using namespace std;
const int N=10005;
const int M=1500;
const int K=10000;
struct node
{
short int a[M];
int I;
}ans[N];
void equ(int l1,int l2)
{
ans[l1].I=ans[l2].I;
for(int i=ans[l1].I-1;i>=0;--i)
ans[l1].a[i]=ans[l2].a[i];
}
void add(int l1,int l2)
{
int k=max(ans[l1].I,ans[l2].I);
for(int i=0;i<k;++i)
{
ans[l1].a[i]+=(ans[l2].a[i]);
if(ans[l1].a[i]>=K)
{ans[l1].a[i]-=K;++ans[l1].a[i+1];}
}
if(ans[l1].a[k]>0)
++k;
ans[l1].I=k;
}
void sub(int l1,int l2)
{
int k=ans[l1].I;
for(int i=0;i<k;++i)
{
ans[l1].a[i]-=(ans[l2].a[i]);
if(ans[l1].a[i]<0)
{ans[l1].a[i]+=K;--ans[l1].a[i+1];}
}
while(ans[l1].a[k-1]==0)
--k;
ans[l1].I=k;
}
void print(int x)
{
for(int i=ans[x].I-1;i>=0;--i)
{
int k=ans[x].a[i];
if(i<ans[x].I-1)
for(int j=0;j<4;++j)
{
if(k==0)
printf("0");
else
k=k/10;
}
if(ans[x].a[i])
printf("%d",ans[x].a[i]);
}
printf("\n");
}
int main()
{
//freopen("data","r",stdin);
int n,m;
while(scanf("%d %d",&n,&m)!=EOF)
{
int k=n+1;
for(int i=0;i<=n+1;++i)
{
ans[i].I=0;
for(int j=0;j<M;++j)
ans[i].a[j]=0;
}
ans[0].a[0]=1;
ans[0].I=1;
equ(k,0);
for(int i=1;i<=n;++i)
{
equ(i,k);
add(k,i);
if(i-m-1>=0)
sub(k,i-m-1);
}
print(k);
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
