标签归档:dynamic programming

猫狗大战

问题描述
【描述 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;
}

小胖办证

问题描述
【描述 Description 】

xuzhenyi要办个签证。办证处是一座M层的大楼,1<=M<=100。 每层楼都有N个办公室,编号为1..N(1<=N<=500)。每个办公室有一个签证员。 签证需要让第M层的某个签证员盖章才有效。 每个签证员都要满足下面三个条件之一才会给xuzhenyi盖章: 1. 这个签证员在1楼 2. xuzhenyi的签证已经给这个签证员的正楼下(房间号相同)的签证员盖过章了。 3. xuzhenyi的签证已经给这个签证员的相邻房间(房间号相差1,楼层相同)的签证员盖过章了。 每个签证员盖章都要收取一定费用,这个费用不超过1000000000。 找出费用最小的盖章路线,使签证生效 【输入格式 Input Format 】 第1行两个整数M和N。 接下来M行每行N个整数,第i行第j个数表示第i层的第j个签证员收取的费用。 【输出格式 Output Format】 按顺序打出你经过的房间的编号,每行一个数。 如果有多条费用最小的路线,输出任意一条。 【样例输入 Sample Input 】 3 4 10 10 1 10 2 2 2 10 1 10 10 10 【样例输出 Sample Output】 3 3 2 1 1 【算法分析】 DP顺序:从下到上,再从左到右,再从右到左 【代码】

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
73
74
75
76
77
78
79
#include <stdio.h>
#include <string.h>
#define M 101
#define N 501
int a[M][N], x[M][N], y[M][N], f[M][N];
 
void print(int xx, int yy)
{
       if (xx < 1 || yy < 1)
              return ;
       print(x[xx][yy], y[xx][yy]);
       printf("%d\n", yy);
}
 
int main()
{
 
       int m, n, i, j, min, flag;
       scanf("%d%d", &m, &n);
 
       for (i = 1; i <= m; i++)
       {
              for (j = 1; j <= n; j++)
                     scanf("%d", &a[i][j]);
       }
 
       memset(x, 0, sizeof(x));
       memset(y, 0, sizeof(y));
       memset(f, 0, sizeof(f));
 
       for (j = 1; j <= n; j++)
       {
              f[1][j] = a[1][j];
       }
 
       for (i = 2; i <= m ; i++)
       {
              for (j = 1; j <= n; j++)
              {
                     f[i][j] = f[i - 1][j] + a[i][j];
                     x[i][j] = i - 1;
                     y[i][j] = j;
              }
 
              for (j = 2; j <= n; j++)
              {
                     if (a[i][j] + f[i][j - 1] < f[i][j])
                     {
                            f[i][j] = a[i][j] + f[i][j - 1];
                            x[i][j] = i;
                            y[i][j] = j - 1;
                     }     
              }
 
              for (j = n - 1; j >= 1; j--)
              {
                     if (a[i][j] + f[i][j + 1] < f[i][j])
                     {
                           f[i][j] = a[i][j] + f[i][j + 1];
                            x[i][j] = i;
                            y[i][j] = j + 1;
                     }
              }
       }
 
       min = 2000000000;
 
       for (i = 1; i <= n; i++)
       {
              if (f[m][i] < min)
              {
                     min = f[m][i];
                     flag = i;
              }
       }
 
       print(m, flag);
       return 0;
}