閱讀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