首页 > 代码库 > hdu acm 2154(多解取一解)

hdu acm 2154(多解取一解)

//题目中结果有一条限制就是最后必须跳回A,如果我们的思想框在这个条件上就很容易卡住,因为这样的条件下的路径很难有规律的罗列,然而我们说这个图形中有三个区域,我们算出每个区域的第n-1次的种类数,然后很容易就地推出了第n次的,取结果的时候只要去A区域的就可以了#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<string>using namespace std;long long int dp[65];int main(void){    int i,j;    int t;    int dpA[1001],dpB[1001],dpC[1001];    dpA[1]=0;dpB[1]=1;dpC[1]=1;    for(i=2;i<=1000;i++)    {        dpA[i]=(dpB[i-1]+dpC[i-1])%10000;        dpB[i]=(dpA[i-1]+dpC[i-1])%10000;        dpC[i]=(dpA[i-1]+dpB[i-1])%10000;    }    while(cin>>t&&t)    {        cout<<dpA[t]<<endl;    }    return 0;}

 

//题目中结果有一条限制就是最后必须跳回A,如果我们的思想框在这个条件上就很容易卡住,因为这样的条件下的路径很难有规律的罗列,然而我们说这个图形中有三个区域,我们算出每个区域的第n-1次的种类数,然后很容易就地推出了第n次的,取结果的时候只要去A区域的就可以了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
long long int dp[65];
int main(void)
{
    int i,j;
    int t;
    int dpA[1001],dpB[1001],dpC[1001];
    dpA[1]=0;dpB[1]=1;dpC[1]=1;
    for(i=2;i<=1000;i++)
    {
        dpA[i]=(dpB[i-1]+dpC[i-1])%10000;
        dpB[i]=(dpA[i-1]+dpC[i-1])%10000;
        dpC[i]=(dpA[i-1]+dpB[i-1])%10000;
    }
    while(cin>>t&&t)
    {
        cout<<dpA[t]<<endl;
    }
    return 0;
}

hdu acm 2154(多解取一解)