hdu 4669 动态规划

思路：主要就是一个动态方程dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];我用的是滚动数组。其实也就是dp[i][(j*Exp[len[num[i]]]+num[i])%k]+=dp[i-1][j];

唯一需要注意的就是存在长度长于n的串，要减掉。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define Maxn 100010
using namespace std;
int len[Maxn],Exp[Maxn*3],n,k,num[Maxn];
int dp[3][210];
void init()
{
    int i;
    for(i=0;i<10;i++) len[i]=1;
    for(i=10;i<100;i++) len[i]=2;
    for(i=100;i<1000;i++) len[i]=3;
    for(i=1000;i<=2000;i++) len[i]=4;
}
int main()
{
    int i,j;
    init();
    //freopen("ans.txt","r",stdin);
    //freopen("ABCd.txt","w",stdout);
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        Exp[0]=1;
        for(i=1;i<=4*n;i++)
            Exp[i]=(Exp[i-1]*10)%k;
        for(i=1;i<=n;i++)
            scanf("%d",num+i);
        int sum=0,s=0;
        int ans=0;
        int pre=1,now=0;
        for(i=1;i<=n;i++)
        {
            now=!now;
            pre=!pre;
            memset(dp[now],0,sizeof(dp[now]));
            for(j=0;j<k;j++)
                dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];
            dp[now][num[i]%k]++;
            sum=(sum*Exp[len[num[i]]]+num[i])%k;
            s+=len[num[i]];
            ans+=dp[now][0];
        }
        for(i=1;i<n;i++)
        {
            now=!now;
            pre=!pre;
            memset(dp[now],0,sizeof(dp[now]));
            for(j=0;j<k;j++)
                dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];
            sum=(sum*Exp[len[num[i]]]+num[i])%k;
            dp[now][sum]--;
            sum=((sum-num[i]*Exp[s])%k+k)%k;
            ans+=dp[now][0];
        }
        printf("%d
",ans);
    }
    return 0;
}