标签归档：dynamic programming

最小矩阵和

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 】

　　给定一个信封，最多只允许粘贴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;
}