nyoj 104最大和

2548 ワード

ダイナミック？プログラム

最大合計
時間制限:1000 ms|メモリ制限:65535 KB
説明
整数からなる2次元行列(r*c)が与えられ、このサブ行列内のすべての要素の和が最大になるように、そのサブ行列を見つける必要があり、このサブ行列を最大サブ行列と呼ぶ.例:0-2-7 0 9 2-6 2-4 1-4 0-2
9 2-4 1-18要素の合計は15です.
入力
1行目には、n組のテストデータがあることを示す整数n(0各テストデータのセット:
第1行には2つの整数r,c(0その後、r行があり、各行にc個の整数がある.
しゅつりょく
出力マトリクスの最大サブマトリクスの要素の和.
サンプル入力

サンプル出力

分析:直接シミュレーションはタイムアウトし、動的計画アルゴリズムを使用する必要があります.
配列bが配列aのi~j(i~j(0<=i<=j<=n-1)i~j(0<=i<=j<=n-1)に対応する列要素と

配列a
0
1
2
...
n-1
i行目
ai0
   ai1
ai2
...
ai,n-1
...
...
...
...
...
...
j行目
aj0
aj1
aj2
...
aj,n-1

配列b
b0
b 1
b2
...
bn-1

2 Dダイナミックプランニングアルゴリズムの概略図
次に、配列bに対して最大文字列和を計算し、これにより、2つの動的計画問題を1つの動的計画問題に変換する.

<span style="font-size:18px;">#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

int a[110][110],b[110];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,i,j,k;
        memset(a,0,sizeof(a));
        scanf("%d %d",&n,&m);
        for(i = 0 ; i < n ; i ++ )
            for(j = 0 ; j < m ; j ++)
            scanf("%d",&a[i][j]);
        int max=-9999;
        for(i = 0 ; i < n ; i ++)
        {              //  b  i~j        
                       //                    
            memset(b,0,sizeof(b));
            for(j = i ; j < n ; j ++)
           {            //       b             
                int sum = 0;
            for(k = 0 ; k < m ; k ++)
            {
                b[k] += a[j][k];
                sum += b[k];
              if(sum > max)
                    max = sum;
              if(sum < 0)
                    sum = 0;

            }
           }
        }
        printf("%d
",max);
    }
    return 0;
}</span>

linuxファイルとファイルシステムの圧縮とパッケージング

python ddtによるデータ駆動