Vijos-1488街灯の改築計画動態計画重慶一中高2018級競技班第9回試験2016.9.10 Problem 3

【問題の説明】華師一の敏行路には、いくつかのきれいな街灯が新設され、学生たちの夜の外出に大きな便利さをもたらした.しかし、それに伴って問題が発生した.
ある晩、OI組のFHHさんが校門の外に歩いていると、急に目の前が真っ暗になり、眼鏡を落としてしまい、二度と見つからなかった.その後、FHHさんは学校の管理所から昨夜街灯が突然消えたのは、回路が重荷に耐えられず、空気スイッチがブレーキを切ったからだと知った.
よく考えるFHHさんは街灯を改築して、再びこのような問題が発生しないようにすることを考えています.FHHさんは各街灯の消費電力a[i]と照明度z[i]をよく知っている.このような前提を満たすように照明度をできるだけ大きくし、最後にM群の最大照明度の和を算出する.各グループの消費電力の制限により、グループ内のいくつかの電灯は使用されない可能性があるが、グループのランプの数として計算すべきである.特に、電灯は順番に与えられ、隣接するいくつかのランプを1つのグループに分けるしかないことに注意してください.
計算が複雑なので、FHHさんは繰り返し計算しても結果が確定しません.今、彼のためにプログラムを書いてこの問題を解決してください.
【入力形式】1行目の3つの整数は、それぞれN、M、Tを表す.次のN行は、行ごとに2つの整数であり、i+1行目はa[i]およびz[i]を表す.
【出力形式】最大照明度を表す整数.
【入力サンプル】

5 2 2
1 1
2 2
3 3
4 4
5 5

【出力サンプル】

10

【データ範囲】70%のデータに対して、2<=N<=80、1<=M<=35、1<=T、a[i]、z[i]<=35が保証される.全てのデータについて、2<=N<=160、1<=M<=50、1<=T、a[i]、z[i]<=50が保証される.
構想:g[i][j]:iからjまでの街灯を一組に分ける最大照明度を表す.f[i][j]:前のi個のランプをj組に分ける最大照明度を表す.f[i][j]=max(f[k][j-1]+g[k+1][i]).

#include
#include
#include
using namespace std;

int n,m,t;
int a[165],z[165];
int f[165][55],g[165][165],x[8500];

int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&z[i]);
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=(n-i+1)*t;j++)
        {
            x[j]=-1;
        }
        for(int j=i;j<=n;j++)
        {
            for(int k=(n-i+1)*t;k>=a[j];k--)
            {
                if(x[k-a[j]]>-1) x[k]=max(x[k],x[k-a[j]]+z[j]);
            }
            for(int k=0;k<=(j-i+1)*t;k++)
            {
                g[i][j]=max(g[i][j],x[k]);
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=min(i,m);j++)
        {
            for(int k=j-1;k1]+g[k+1][i]);
            }
        }
    }

    printf("%d
",f[n][m]);
    return 0;
}