首页 > 其他 > 详细

code froce 577B DP

时间:2015-11-27 10:42:43      阅读:315      评论:0      收藏:0      [点我收藏+]

给两个数n(n <= 1e6), m ( m <= 1e3 ), 问能否在n个数里找到一些数 让他们的和相加能被m整除

思路: 把所有的n变为在m的剩余系下的数

1. n > m 此时在m的剩余系下一定存在两个相等的数 那他们之差一定是0 所以此时一定存在能被m整除 (抽屉原理)

2. n <= m

跟01背包问题类似 

DP设计的转移方程为

f[i][j] = f[i - 1][j] || f[i - 1][(j - a + m) % m]

前一个式子指在前面的所有数中是否存在和被m整除

第二个式子指在前面所有数中是否存在一个和加上当前这个数字能被m整除 (j != a)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int MaxN = 1000;
 8 int a, n, m;
 9 bool f[MaxN + 5][MaxN + 5];
10 
11 int main()
12 {
13     scanf("%d %d", &n, &m);
14     if (n > m)
15     {
16         printf("YES");
17         return 0;
18     }
19     else
20     {    
21         for (int i = 1; i <= n; i++)
22         {
23             scanf("%d", &a); a %= m;
24             f[i][a] = 1;
25             for (int j = 0; j <= m - 1; j++)
26             if (j != a) f[i][j] = f[i - 1][j] || f[i - 1][(j - a + m) % m];
27         }
28         printf(f[n][0] ? "YES" : "NO");
29     }
30 }

 

code froce 577B DP

原文:http://www.cnblogs.com/wns0108/p/4999349.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!