Uva562(dp)

给我们n个硬币

每个硬币都有它的面值，要我我们分为两堆硬币，使得硬币的差值最小

我们可以dp计算出所有的差值，然后从小到大枚举差值，如果差值存在，就输出

dp[i][j] 表示对于前i件物品能达到差值j

状态转移方程为 if(dp[i-1][j]==1) dp[i][j] = 1（不选第i个物品），dp[i][abs(j-2*a[i])] = 1(选第i件物品）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;                   
16 const int INF = 1<<30;
17 /*
18 
19 */
20 const int N = 100 + 10;
21 int a[N];
22 int dp[N][50000+10];//dp[i][j] 表示对于对于前i个物品，差值为j是否存在,  然后算出所有可能的差值 
23 int main()
24 {
25     int t, n, i, j, sum;
26     scanf("%d", &t);
27     while (t--)
28     {
29         scanf("%d", &n);
30         sum = 0;
31         for (i = 1; i <= n; ++i)
32         {
33             scanf("%d", &a[i]);
34             sum += a[i];
35         }
36         
37         memset(dp, 0, sizeof(dp));
38 
39         dp[0][sum] = 1;
40         for (i = 1; i <= n; ++i)
41         {
42             for (j = 0; j <= sum; ++j)
43             {
44                 if (dp[i - 1][j])
45                 {
46                     dp[i][j] = 1;
47                     dp[i][abs(j - 2 * a[i])] = 1;
48                 }
49             }
50         }
51         for (j = 0; j <= sum; ++j)//从小到大枚举差值
52         if (dp[n][j])
53             break;
54         printf("%d
", j);
55     }
56     return 0;
57 }

View Code

http://ncc.neuq.edu.cn/oj/problem.php?id=1457

t 数据组数

n k k表示最多能交换k个数字

n个数字 -100<=数字<=100

n个数字

问我们最多交换k次两堆数字中对应的数字，问我们能达到的最小差值，

我们可以计算出第一堆数据所能达到的所有状态，并记录其交换的次数

dp[i][j] = k 表示对于前i个数字，交换了k次，能达到状态j

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <map>
10 #include <set>
11 #include <string>
12 #include <math.h>
13 using namespace std;
14 #pragma warning(disable:4996)
15 typedef long long LL;                   
16 const int INF = 1<<30;
17 /*
18 
19 */
20 const int N = 100 + 10;
21 int a[N], b[N];
22 int dp[N][20000 + 10];//dp[i][j] 表示前i件物品，能使得陈船长的好玩度为j
23 int main()
24 {
25     int t, n, k, i, j;
26     int sum;
27     scanf("%d", &t);
28     while (t--)
29     {
30         scanf("%d%d", &n, &k);
31         sum = 0;
32         for (i = 1; i <= n; ++i)
33         {
34             scanf("%d", &a[i]);
35             a[i] += 100;
36             sum += a[i];
37         }
38         for (i = 1; i <= n; ++i)
39         {
40             scanf("%d", &b[i]);
41             b[i] += 100;
42             sum += b[i];
43         }
44         
45         for (i = 1; i <= n; ++i)
46         for (j = 0; j <= sum; ++j)
47             dp[i][j] = INF;
48         dp[1][a[1]] = 0;
49         dp[1][b[1]] = 1;
50         for (i = 2; i <= n; ++i)
51         {
52             for (j = 0; j <= sum; ++j)//算出第一堆数字总和达到j需要的交换次数
53             {
54                 if (j >= a[i])//不交换第i个数字, j-a[i]为上一层所能达到的总和
55                     dp[i][j] = min(dp[i][j], dp[i-1][j - a[i]]); 
56                 if (j >= b[i])//交换第i个数字，j-b[i]为上一层所能达到的总和
57                     dp[i][j] = min(dp[i][j], dp[i-1][j - b[i]] + 1);
58             }
59         }
60         int ans = INF;
61         for (i = 0; i <= sum; ++i)
62         {
63             if (dp[n][i] <= k)
64                 ans = min(ans, abs(sum - 2 * i));
65         }
66         printf("%d
", ans);
67     }
68     return 0;
69 }

View Code