标签归档：动态规划

邮票面值设计

发表回复

【问题描述】
【描述 Description 】

　　给定一个信封，最多只允许粘贴N张邮票，计算在给定M（N+M<=10）种邮票的情况下（假定所有的邮票数量都足够）,如何设计邮票的面值，能得到最大max ，使得1～max之间的每一个邮资值都能得到。 例如，N=3，M＝2，如果面值分别为1分、4分，则在l分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）：如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当N=3，M＝2时，7分就是可以得到连续的邮资最大值，所以MAX=7，面值分别为l分、3分。 【样例输入】 共一行，两个整数，分表为N与M的值。 【输入格式 Input Format 】 一行，分别为N,M。 【输出格式 Output Format 】 两行。 第一行为m种邮票的面值，按升序排列，各数之间用一个空格隔开。 第二行为最大值。 【样例输入 Sample Input 】 3 2 【样例输出 Sample Output 】 1 3 MAX=7 算法分析 深搜加DP 栈记录所用邮票的面值 每次面值的搜索的范围为：上一次使用的邮票面值+1 to 上一次连续达到的最大值+1 然后DP，记录达到每个面值用的最少邮票数，不断更新最优解 注意要从第1张邮票开始，否则要出错 【代码】 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include <stdio.h>
 
int a[11], ans[11];
int b[1001];
int n, m, max;
 
int dp(int i)
{
       int j, k;
 
       for (j = 1; j < 1001; j++)
              b[j] = 9999;
 
       for (j = 1; j <= i; j++)
              b[a[j]] = 1;
       j = 0;
 
       do
       {
              j++;
 
              for (k = 1; k <= i; k++)
                     if (j > a[k] && b[j - a[k]] + 1 < b[j])
                            b[j] = b[j - a[k]] + 1;
 
       }while (b[j] <= m);
       return j;
}
 
void search(int i)
{
       int j, k;
 
       if (i > n)
       {
              if (dp(i - 1) - 1 > max)
              {
                     for (j = 1; j <= 10; j++)
                            ans[j] = a[j];
                     max = dp(i - 1) - 1;
              }
              return;
       }
       j = dp(i - 1);
 
       for (k = j ; k >= a[i - 1] + 1; k--)
       {
              a[i] = k;
              search(i + 1);
       }
}
 
int main()
{
 
       int i;
       scanf("%d%d", &m, &n);
 
       max = 0;
       a[1] = 1;
       search(2);
 
       for (i = 1; i <= n; i++)
              printf("%d ", ans[i]);
 
       printf("\n");
       printf("MAX=%d\n", max);
       return 0;
}

猫狗大战

发表回复

问题描述
【描述 Description】
　　新一年度的猫狗大战通过SC(星际争霸)这款经典的游戏来较量，野猫和飞狗这对冤家为此已经准备好久了，为了使战争更有难度和戏剧性，双方约定只能选择Terran(人族)并且只能造机枪兵。

　　比赛开始了，很快，野猫已经攒足几队机枪兵，试探性的发动进攻；然而，飞狗的机枪兵个数也已经不少了。野猫和飞狗的兵在飞狗的家门口相遇了，于是，便有一场腥风血雨和阵阵惨叫声。由于是在飞狗的家门口，飞狗的兵补给会很快，野猫看敌不过，决定撤退。这时飞狗的兵力也不足够多，所以没追出来。

　　由于不允许造医生，机枪兵没办法补血。受伤的兵只好忍了。555－
　　现在，野猫又攒足了足够的兵力，决定发起第二次进攻。为了使这次进攻给狗狗造成更大的打击，野猫决定把现有的兵分成两部分，从两路进攻。由于有些兵在第一次战斗中受伤了，为了使两部分的兵实力平均些，分的规则是这样的：1）两部分兵的个数最多只能差一个；2）每部分兵的血值总和必须要尽可能接近。现在请你编写一个程序，给定野猫现在有的兵的个数以及每个兵的血格值，求出野猫按上述规则分成两部分后每部分兵的血值总和。

【输入格式 Input Format】
第一行为一个整数n(1<=n<=200)，表示野猫现在有的机枪兵的个数。以下的n行每行一个整数，表示每个机枪兵的血格(1<=ai<=40)。 【输出格式 Output Format 】 只有一行，包含两个数，即野猫的每部分兵的血值总和，较小的一个值放在前面，两个数用空格分隔。 【样例输入 Sample Input 】 3 35 20 32 【样例输出 Sample Output】 35 52 【算法分析】 1 to n div 2为前一半数，n div 2+1 to n为后一半数之后枚举a[i],a[j]看是否可以交换 代码 方法一： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <stdio.h>
 
int abs(int t)
{
 
       if (t < 0)
              return -t;
       else
              return t;
}
 
int main()
{
 
       int a[201], b[201];
       int n, i, j, l1, l2, sum1 , sum2, temp;
 
       scanf("%d", &n);
 
       l1 = n / 2;
       l2 = n - l1;
       sum1 = 0;
       sum2 = 0;
 
       for (i = 1; i <= l1; i++)
       {
              scanf("%d", &a[i]);
              sum1 += a[i];
       }
 
       for (i = 1; i <= l2; i++)
       {
              scanf("%d", &b[i]);
              sum2 += b[i];
       }
 
       for (i = 1; i <= l1; i++)
       {
              for (j = 1; j <= l2; j++)
              {
                     if (abs((sum1 + b[j] - a[i]) - (sum2 + a[i] - b[j])) < abs(sum1 - sum2))
                     {
                            sum1 = sum1 + b[j] - a[i];
                            sum2 = sum2 + a[i] - b[j];
                            temp = a[i];
                            a[i] = b[j];
                            b[j] = temp;
                     }
              }
       }
 
       if (sum1 < sum2)
              printf("%d %d\n", sum1, sum2);
       else
              printf("%d %d\n", sum2, sum1);
 
       return 0;
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Const
maxn=200;
maxm=8000;
Var
f:array[0..maxn,0..maxm] of boolean;
 
n,ans,mid:integer;
d:array[1..maxn] of integer;
 
Procedure Init;
var i:integer;
begin
　　fillchar(f,sizeof(f),false);
　　f[0,0]:=true;
　　ans:=0;
　　readln(n);
　　for i:=1 to n do readln(d[i]);
　　for i:=1 to n do ans:=ans+d[i];
　　mid:=ans div 2;
end;
 
Procedure Work;
var i,j,k:integer;
 
begin
　　for i:=1 to n do
　　  for k:=i downto 1 do
　　　　for j:=mid-d[i] downto 0 do
　　　　  if f[k-1,j] then f[k,j+d[i]]:=true;
end;
 
Procedure Print;
 
var i,j:integer;
begin
　　i:=0;j:=0;
　　while (not f[n div 2,mid+j]) do dec(j);
　　j:=mid+j;
　　writeln(j,' ',ans-j);
end;
 
BEGIN
init;
work;
print;
END.

三取方格数

发表回复

【问题描述】
背景 Background
JerryZhou同学经常改编习题给自己做。

这天，他又改编了一题。。。。。

【描述 Description】
设有N*N的方格图，我们将其中的某些方格填入正整数，

而其他的方格中放入0。
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

【输入格式 Input Format】

第一行:N (4<=N<=20) 接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0 【输出格式 Output Format】 一行，表示最大的总和。 【样例输入 Sample Input】 4 1 2 3 4 2 1 3 4 1 2 3 4 1 3 2 4 样例输出 Sample Output 39 注释 Hint 多进程DP 算法分析 可以用网络流来做 由于没做二取方格数；我一开始用一般DP；DP一次则把走过的路删去；3次DP； 只对了一组；看了题解后知道了我的算法虽然保证了3次DP的最优；但并不代表全局最优；是有反例的...... 其实可以用压缩数组的方法..因为每一阶段都只与上一阶段有关..滚动滚动数组..循环利用..不断再生..节约环保..{好像扯远了...-_-#}..不过节约时间起见..其实不用滚动数组也可以以0ms过掉.. 　　做这条题时很深刻地感受得到..这条题是斜着划分阶段的..太伟大了啦..而且由于每一阶段中..横坐标与纵坐标有一种莫名的内在关系..所以为数组节约了不少维..{不过就算不节约..N<=20..也应该不会超..}.. 用sum[k,x,y,z]表示当走到第K步时,且三人横坐标分别为X,Y,Z时..所取数的最大值..由于每一个人都可以由2个方向推来..所以一共有2^3=8种状态.. sum[k,x,y,x]=max(sum[k,x,y,z],sum[k-1,x+f[i,1],y+f[i,2],z+f[i,3]]) 且由于第K步只能到达横坐标<=min(k,n)的点..所以其实循环时可以节约节约.. 注意:每一格只能取一次..数组的大小.. 【代码】 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
int min(int a, int b)
{
 
       if (a < b)
              return a;
       else
              return b;
 
}
 
int f[41][21][21][21], a[21][21];
 
int main()
{
 
       int n, i , j, k, x1, x2, x3, temp, s1, s2, s3;
       scanf("%d", &n);
 
       for (i = 1; i <= n; i++)
       {
              for (j = 1; j <= n; j++)
                     scanf("%d", &a[i][j]);
 
       }
 
       memset(f, 0, sizeof(f));
       f[1][1][1][1] = a[1][1];
 
       for (k = 2; k <= n + n -1; k++)
       {
              for (x1 = 1; x1 <= min(k, n); x1++)
              {
 
                     for (x2 = 1; x2 <= min(k, n); x2++)
                     {
                            for (x3 = 1; x3 <= min(k, n); x3++)
                            {
                                   temp = a[k - x1 + 1][x1] + a[k - x2 + 1][x2] + a[k - x3 + 1][x3];
 
                                   if (x1 == x2)
                                          temp -= a[k - x1 + 1][x1];
 
                                   if (x1 == x3)
                                          temp -= a[k - x1 + 1][x1];
 
                                   if (x2 == x3)
                                          temp -= a[k - x2 + 1][x2];
 
                                   if (x1 == x2 && x1 == x3)
                                          temp += a[k - x1 + 1][x1];
 
                                   for (s1 = -1; s1 <= 0; s1++)
                                   {
                                          for (s2 = -1; s2 <= 0; s2++)
                                          {
                                                 for (s3 = -1; s3 <= 0; s3++)
                                                 {
                                                        f[k][x1][x2][x3] = max(f[k][x1][x2][x3], f[k - 1][x1 + s1][x2 + s2][x3 + s3] + temp);
                                                 }
                                          }
                                   }
                            }
                     }
              }
       }
 
       printf("%d\n", f[n + n - 1][n][n][n]);
       return 0;
}