poj 1745 - Divisibility

古城微笑少年丶 2022-06-08 08:15 129阅读 0赞

# 1. 地址 #

[http://poj.org/problem?id=1745][http_poj.org_problem_id_1745]

# 2. 定位 #

*  动态规划

# 3. 分析 #

## 3.1 状态转移 ##

一般情况下，dp 数组的存储内容就是求解目标，在本题中，求解目标为能否被 K 整除，即逻辑是否。

状态转移的理论依据是，和的余数与余数之和同余。

dp\[i\]\[j\] 表示前 i 个数字加减运算后，运算结果的余数是否为 j，它可以在前 i−1 个数字运算结果余数为 j 的基础上，加减 num\[i\] 并取余后得到。

状态转移方程为：

dp\[i\]\[(j\+num\[i\])%K\]=true

当且仅当，dp\[i−1\]\[j\]==true，即存在前 i−1 个数字运算结果余数为 j。

边界条件：dp\[0\]\[0\]==true，即前0个数字运算结果为0，其余数为0。

## 3.2 存储空间优化 ##

dp\[i\]\[j\] 仅与 dp\[i−1\]\[\] 有关，故可以进行存储空间优化。状态转移方程中，状态更新是前后两个方向的，因此，一维数组无法胜任存储需求，采用双一维数组存储。

在滚动存储的过程中，状态改变不是全覆盖的，需要进行数据置位。

# 4. 代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    int weight[10001];
    int dp[2][10001];
    
    int main()
    {
        int N,K;
        int i,j;
    
        scanf("%d %d",&N,&K);
        memset(weight,0,sizeof(weight));
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(i=1; i<=N; i++)
        {
            scanf("%d*c",&weight[i]);
        }
        for(i=1; i<=N; i++)
        {
            for(j=0; j<K; j++)
            {
                dp[i%2][j] = 0;
            }
            for(j=0; j<K; j++)
            {
                if(dp[(i-1)%2][j])
                {
                    dp[i%2][abs(j+weight[i])%K] = 1;
                    dp[i%2][abs(j-weight[i])%K] = 1;
                }
            }
        }
        if(dp[(i-1)%2][0])
        {
            printf("Divisible\n");
        }
        else
        {
            printf("Not divisible\n");
        }
        return 0;
    }

# 5. 性能 #

<table> 
 <thead> 
  <tr> 
   <th align="center">Exe.Time</th> 
   <th align="center">Exe.Memory</th> 
   <th align="center">Code Length</th> 
   <th align="center">Language</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">219MS</td> 
   <td align="center">544K</td> 
   <td align="center">751B</td> 
   <td align="center">c</td> 
  </tr> 
 </tbody> 
</table>

Ver 1.0 2017-9-19

[http_poj.org_problem_id_1745]: http://poj.org/problem?id=1745