标签归档：DP

最小矩阵和

2条回复

很久很久以前的代码，在某个角落找到，贴了上来，
在杭电acm1081上可以ac，来源应该是Greater New York 2001
貌似作为中南赛区ACM竞赛题

问题描述
【Description】

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

is in the lower left corner:

9 2
-4 1
-1 8
and has a sum of 15.

【Input】

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

【Output】

Output the sum of the maximal sub-rectangle.

【Sample Input】
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

【Sample Output】
15

下面的中文来自：http://blog.csdn.net/hym666/archive/2010/08/17/5818591.aspx
此文章处有C++的解答

题目描述：
在一个大的方阵中找出一个子方阵，这个子方阵是所有子方阵和中的最大的一个
问题分析：
问题可以回归到一个数列中的连续字数列的和的最大值。
即把每一行看成一个数列。把每一列转换成一个数。
当然每一列也是一个数列，有很多的连续子数列。所有会有很多中情况。可穷举各种数列来构造一个行向的数列。
再用动态规划计算每一行的最大值，再在各行中选取最大的作为题目的解。

【代码】

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

import java.util.*;
 
public class Main {
 
       /**
        * @param args
        */
 
       public static int maxSum(int[] b, int n){
 
              int max = b[0], sum = 0;
 
              for (int i = 1; i < n ; i++ ){
                     if (max > 0)
                            max += b[i];
                     else
                            max = b[i];
 
                     if (max > sum)
                            sum = max;
              }
              return sum;
       }
 
       public static int maxTotal(int[][] a, int n){
 
              int max = 0;
              int[] b = new int[n];
 
              for (int i = 0; i < n; i++){
                     for (int j = 0; j < n; j++)
                            b[j] = a[i][j];
 
                     int sum = maxSum(b, n);
 
                     if (sum > max)
                            max = sum;
 
                     for (int j = i + 1; j < n; j++){
                            for (int k = 0; k < n; k++)
                                   b[k] += a[j][k];
 
                            sum = maxSum(b, n);
                            if (sum > max)
                                  max = sum;
                     }
              }
              return max;
       }
 
       public static void main(String[] args) {
              // TODO Auto-generated method stub
 
              Scanner cin = new Scanner(System.in);
              int n;
 
              while (cin.hasNext()){
                     n = cin.nextInt();
                     int[][] a = new int[n][n];
                     for (int i = 0; i < n; i++){
                            for (int j = 0; j < n; j++){
                                   a[i][j] = cin.nextInt();                                  
                            }
                     }
                     System.out.println(maxTotal(a, n));
              }
       }
}

垃圾陷阱

发表回复

问题描述
【Description】

卡门——农夫约翰极其珍视的一条Holsteins奶牛——已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D (2 <= D <= 100)英尺。 卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。 每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。 假设卡门预先知道了每个垃圾扔下的时间t(0a then a:=b。

　　这道题可以用DP解决。用l[i,j]表示掉下来i个垃圾后，卡门爬上的高度为j时她最长的寿命。显然l[0,0]=10。对于任一个状态l[i-1,j]，若l[i-1,j]>=g[i].time，说明这个状态的卡门能够坚持到下一个垃圾下落。在这种情况下，按以下两种方法处理第i个垃圾，即进行状态转移：

吃掉第i个垃圾，即update(l[i,j],l[i-1,j]+g[i].life)；

用第i个垃圾来垫高。令t=j+g[i].height，即把第i个垃圾用来垫高后卡门爬上的总高度。如果t>=d，则卡门于g[i].time时爬了出来，否则update(l[i,t],l[i-1,j])。

　　若首次遇到某一个l[i,0]一次也没有赋值，说明卡门不可能坚持到第i个垃圾下落，则她最多可以存活的时间为l[i-1,0]（即把前i-1个垃圾全吃掉后的寿命）。

　　注意到在计算l数组的第i行时只用到了第i-1行，因此l数组可用滚动数组来实现。

【代码】

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <stdio.h>
#include <string.h>
 
#define MAXN 101
#define max(a,b) a>b?a:b
 
typedef struct node
{
       int time, life, height;
}node;
 
int main()
{
 
       node a[MAXN], temp;
       int flag;
 
       int f[MAXN][MAXN * 10];
       int n, d, i, j, k, t, maxt, m;
 
       scanf("%d%d", &d, &n);
       maxt = 0;
 
       for (i = 1; i <= n; i++)
       {
              scanf("%d%d%d", &a[i].time, &a[i].life, &a[i].height);
       }
 
       for (i = 1; i < n; i++)
       {
 
              for (j = i + 1; j <= n; j++)
              {
 
                     if (a[i].time > a[j].time)                                                                 
                     {
                            temp = a[i];
                            a[i] = a[j];
                            a[j] = temp;
 
                     }
              }
       }
 
       memset(f, 0, sizeof(f));
 
       f[0][0] = 10;
       flag = 0;
       maxt = 0;
 
       for (i = 1; i <= n; i++)
       {
 
              m = 0;
              k = 0;
 
              for (j = 0; j <= maxt; j++)
              {
 
                     if (f[i - 1][j] >= a[i].time)
                     {
 
                            f[i][j] = max(f[i][j], f[i - 1][j] + a[i].life);
                            t = j + a[i].height;
 
                            if (t >= d)
                            {
                                   flag = a[i].time;
                                   break;
                            }
 
                            if (t > m)
                                   m = t;
 
                            f[i][t] = max(f[i][t], f[i - 1][j]);
                            k++;
                     }
              }
 
              if (k == 0)
                     break;
 
              if (flag != 0)
                     break;
 
              maxt = m;
       }
 
       if (flag != 0)
              printf("%d\n", flag);
       else
       {
              printf("%d\n", f[i - 1][0]);
       }
       return 0;
}

应该是5年前的代码了，从以前的百度blog中转了过来

猫狗大战

发表回复

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