vijos 1243 ——DP

먼저 DP이며 데이터 강화 버전의 DP입니다.제목: 한동안의 경영 끝에 ddengi의 OI상점은 다른 공급업체로부터 제품을 구매하여 선반에 올리는 것에 만족하지 않고 스스로 제품을 생산하기 시작합니다!제품의 생산은 M단계를 필요로 하며, 각 단계는 N대 기계 중 어느 곳에서든 완성할 수 있지만, 생산 단계는 반드시 엄격하게 순서대로 집행해야 한다.이 N대 기계의 성능이 다르기 때문에, 그것들은 매 단계를 완성하는 데 소요되는 시간도 다르다.기계 i가 j 단계를 완성하는 시간은 T[i, j]이다.반제품을 한 기계에서 다른 기계로 옮기는 데도 시간이 걸린다.아울러 안전과 제품의 품질을 보장하기 위해 기기당 최대 L 단계만 연속으로 완료할 수 있다.즉, 한 기계가 연속으로 제품의 L단계를 완성했다면 다음 단계는 반드시 한 기계를 바꾸어 완성해야 한다는 것이다.지금,ddengi의 OI상점 역사상 첫 번째 제품이 생산되기 시작하는데 가장 짧게는 얼마나 걸릴까요?어느 날Azuki.7 대약동설: 이런 문제는 너무 간단하다. 우리는 문제의 범위를 좀 바꾸자.풋내기의 약동에 대해서 말하자면, 이것은 매우 어려운 문제이다. 그는 네가 그를 도와 이 문제를 해결할 수 있기를 바란다.50%의 데이터에 대해 N<=5, L<=4, M<=10000은 100%의 데이터에 대해 N<=5, L<=50000, M<=100000은 처음에 내가 생각했던 DP 방정식은 다음과 같다. 설정: f[i][j][k]는 제i공정에 대해 제j기계가 하고 이것을 완성하기 위해 k개를 만들었다.전환 가능:
f[i][j][k]=f[i−1][j][k−1]+t[i][j](k>1)
그리고:
f[i][j][k] = min{f[i - 1][p][t]} + cost + t[i][j](k == 1 && t <= L && p != j)
이렇게 하면 틀림없이 50%의 데이터를 통과할 수 있을 것이다. 그리고 나는 저녁에 생각해서 사실 k의 1차원은 아무 소용이 없다는 것을 발견했다. 왜냐하면 우리는 k=1의 상황만 알면 반드시 k>1의 상황을 알 수 있기 때문이다.
그리고 한 단어가 내 머릿속에 떠올랐다.
단조로운 대열.
f[i][j]를 설정하면 i개 공사에서 j개 기계로 하는 최소 비용을 나타낸다.
변환 방정식은 다음과 같습니다.
f[i][j]=min(f[v][p]+sum[v−>i][j]+cost)
접두어 및 최적화:
f[i][j]=min(f[v][p]+sum[i][j]−sum[v][j]+cost)
f[i][j]=min(f[v][p]−sum[v][j])+sum[i][j]+cost;
그리고 곰곰이 생각해 보면 i 앞에 있는 모든 v를 그대로 유지하면: i - v < L이면 된다.
또한 이러한 성격을 유지하는 동시에 O(1) 조회의 합법적인 최소치를 확보하면 된다.
누드의 단조로운 대열이 됐어..
우리는 최소치를 찾을 때 팀 헤드를 직접 가져와 팀 헤드가 합법적인지 확인하고 합법적이지 않으면 팀 헤드를 튀어나와 계속 판정한다.
이 DP 값을 받았을 때 f[i][j]로 다른 대기열을 업데이트하면 됩니다.
그리고 자신이 이 이론을 잘 알지만 문제를 약간 베껴서 풀었는데...

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define Rep(i,n) for(int i = 1;i <= n;i ++)
#define RepG(i,x) for(int i = head[x];~ i;i = edge[i].next)
using namespace std;
void rd(int &x)
{
    x = 0;bool flag = 0;
    char ch = getchar();
    while((ch > '9' || ch < '0') && ch != '-')ch = getchar();
    if(ch == '-')flag = 1,ch = getchar();
    while(ch >= '0' && ch <= '9')x = 10 * x + ch - '0',ch = getchar();
    x = flag ? -x : x;
}
const int N = 100005;
const int inf = int(2e+9) + 1 << 25;
int sum[6][N],m,n,cost,l,f[N][6],q[6][N][2],h[6],t[6];
// f[i][j] = min { f[v][p] - sum[v][j] } + sum[i][j] + k;
int main(){
//  freopen("t1.txt","r",stdin);
    //rd(m),rd(n),rd(cost),rd(l);
    scanf("%d%d%d%d",&m,&n,&cost,&l);
    Rep(i,n)
        Rep(j,m){scanf("%d",&sum[i][j]);/*rd(sum[i][j]);*/sum[i][j] += sum[i][j - 1];}
    Rep(i,m)
        Rep(j,n)
            f[i][j] = inf;
    Rep(i,n)q[i][t[i]][0] = 0;
    Rep(i,m)
    {
        Rep(k,n)
        {
            int Maxn = inf;
            //int v = k,j = k;
            while(h[k]<=t[k] && i-q[k][ h[k] ][0]>l) h[k]++;
            /*int tt=q[k][ h[k] ][0],p=q[k][ h[k] ][1]; f[i][k]=min(f[i][k],f[tt][p]+sum[k][i]-sum[k][tt]+cost); */

            int pos = q[k][h[k]][0],s = q[k][h[k]][1];
            //while(h[k] < t[k] && i - pos > l)h[k] ++;
            f[i][k] = min(f[pos][s] - sum[k][pos] + sum[k][i] + cost,f[i][k]);
        }
        Rep(k,n)
            Rep(j,n) // f[i][j]    q[v]
                if(k != j){
                    while(h[j] <= t[j] && f[i][k]-sum[j][i]<= f[ q[j][t[j]][0] ][q[j][t[j]][1]] - sum[j][q[j][t[j]][0]]) t[j]--;
                    q[j][++ t[j]][0] = i,q[j][t[j]][1] = k;
                }
    }
    int MA = inf;
    Rep(i,n)MA = min(MA,f[m][i]);
    printf("%d
",MA - cost);
    return 0;
}