数据包的调度机制

发表于 更新于 分类于

Problem’s Website

  • 数据包的调度机制

    Solution

  • 这道题是一道区间dp，状态的设法有很多种，可以设f[i][j]为从i到j的最小延迟值，答案为f[1][n]，状态转移时，我们先枚举区间长度l，再分别枚举左右端点i,j，再枚举i-j之间的点k，方程为

    1
    f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[k] * (l - 1) + (sum[j] - sum[k]) * (k - i));

    要注意我们枚举的k表示最后一个出栈的是k，那么前面的出栈的顺序为k—i+1,所以我们可以用前缀和来维护。

    Code

    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
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define INF 0x7fffffff - 1
    using namespace std;
    int sc() {
    	int xx = 0, ff = 1; char cch = gc;
    	while(cch < '0' || cch > '9') {
    		if(cch == '-') ff = -1; cch = gc;
    	}
    	while(cch >= '0' && cch <= '9') {
    		xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    	}
    	return xx * ff;
    }
    int t, n;
    int f[110][110];
    int a[110], sum[110];
    int main() {
    	t = sc();
    	while(t--) {
    		memset(sum, 0, sizeof(sum));
    		memset(f, 0, sizeof(f));
    		n = sc();
    		for(int i = 1; i <= n; i++)
    			a[i]= sc(), sum[i] = sum[i - 1] + a[i];
    		for(int l = 1; l <= n; l++) {
    			for(int i = 1; i <= n - l + 1; i++) {
    				int j = i + l - 1;
    				f[i][j] = INF;
    				for(int k = i; k <= j; k++)
    					f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[k] * (l - 1) + (sum[j] - sum[k]) * (k - i));
    			}
    		}
    		printf("%d\n", f[1][n]);
    	}
    	return 0;
    }

rp++