程序如下
//"div.18"和"div.18"的测试都过不了还AC了，怪
#include <stdio.h>
#include <string.h>

int m,n;
int Opt[10010][110];
int Int[10010];

int DP()
{
    int i,j,s;
    memset(Opt,0,sizeof(Opt));
    Opt[1][Int[1]]=1;
    for(i=1;i<n;i++)
	{
        for(j=0;j<=m;j++)
        {
            if(Opt[i][j])
            {
			//	Opt[i][j]=0;
                s=j+Int[i+1];
                s%=m;
                Opt[i+1][s]=1;
                s=j-Int[i+1];
				s%=m;//加了这句一样的
                while(s<0) 
					s+=m;
                Opt[i+1][s]=1;
            }
        }
    }
    if(Opt[n][0]) 
		return 1;
    return 0;
}
int main()
{
    int Kase=1,i;
	//    scanf("%d",&Kase);
	freopen("div.11", "r", stdin);
    while(Kase--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
		{
            scanf("%d",&Int[i]);
            Int[i]%=m;
            while(Int[i]<0) 
                Int[i]+=m;
        }
        if(DP()) 
			printf("Divisible\n");
        else 
			printf("Not divisible\n");
		if(Kase) 
			printf("\n");
    }
    return 0;
}
测试数据:
46 35
-20 -17 -43 -60 81 -48 -83 -10 44 8 97 62 -5 8 84 34 73 -82 51 -13 -8 28 -56 97 -60 -1 62 -36 89 25 8 -88 81 55 -82 -17 85 39 71 68 60 63 42 13 -61 22

• Re:这组数据过不了,怎么还能AC呢?怪怪..... (1393) 20054738 2007-05-06 03:31:47