阅读303 返回首页    go 阿里云 go 技术社区[云栖]

POJ 1745DP

题解：看了题觉得没什么思路 觉得如果一步一步推肯定超空间了 然后我看了黄学长的博客 啊 用两个数组来回推就行了 太巧妙了 

太弱了我 哎 还是做题不够 学长真是猛。。。

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define get(x) ((x)<0?(-(x))%k:(x)%k)
bool dp[2][105];
int yl[10005];
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=0; i<n; i++)
            scanf("%d",&yl[i]);
        for(int i=0; i<k; i++)
            dp[0][i]=0;
        dp[0][get(yl[0])]=1;
        int g1=1,g2=0;
        for(int i=1; i<n; i++)
        {
            g1=!g1,g2=!g2;
            for(int j=0; j<k; j++)
                dp[g2][j]=0;
            for(int j=0; j<k; j++)
                if(dp[g1][j])
                    dp[g2][get(j+yl[i])]=dp[g2][get(j-yl[i])]=1;
        }
        if(dp[g2][0])
            puts("Divisible");
        else
            puts("Not divisible");
    }
    return 0;
}


最后更新：2017-04-02 00:06:51

  上一篇：go linux文件搜索查找命令
  下一篇：go C#typeof