UVa 11400 Lighting System Design dp : 线性结构上dp LIS

Lighting System Design dp : 线性结构上dp LIS

The question is from here.

My Solution

首先这个题目是要保持总灯泡数不变的，一定是换一个上去才可以，是在这个情况下money-saving，而不管energy-saving。所以把功率小的一些灯泡换成大灯lamp以节约voltage source的钱。

把灯泡的规格按电压从小到大排列，d[ i ] 表示前i种计划中的灯泡的最低总消费。

d[ i ] = min{d[ j ] + (s[ i ] - s[ j ])*c[ i ] + k[ i ] }   这里i > j;

#include 
#include 
//#define LOCAL
using namespace std;
int d[1002],v[1002],vt[1002],k[1002],kt[1002],c[1002],ct[1002],l[1002],lt[1002], s[1002];

void merge_sort(int x, int y)
{
    if(y-x > 1){
        int m = x + (y-x)/2;
        int p = x, q = m, i = x;
        merge_sort(x,m);
        merge_sort(m,y);
        while(p < m || q < y){ if(q >= y || (p < m && v[p] <= v[q])) {
                vt[i] = v[p]; kt[i] = k[p]; ct[i] = c[p]; lt[i] = l[p];
                i++;p++; //最开始的时候这个 ++ 是写在下标里面的常规写法，但这里4个数组按v[]排序，所以只能拿出来单独 ++ 了
            }
            else{
                vt[i] = v[q]; kt[i] = k[q]; ct[i] = c[q]; lt[i] = l[q];
                i++;q++;
            }
        }
        for(int i = x; i < y; i++) {
            v[i] = vt[i]; k[i] = kt[i]; c[i] = ct[i]; l[i] = lt[i];
        }
    }
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt","r",stdin);
    #endif // LOCAL
    int n,sumt;
    while(scanf("%d",&n)&&n != 0){
        sumt = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d%d",&v[i],&k[i],&c[i],&l[i]);
        }
        merge_sort(1,n+1);
        for(int i = 1; i <= n; i++){
            sumt += l[i];
            s[i] = sumt;
        }
        d[0] = 0;s[0] = 0;
        for(int i = 1; i <= n; i++){
			d[i] = d[i-1] + (s[i] - s[i-1])*c[i] + k[i];
			for(int j = 0; j < i; j++){
				d[i] = min(d[i], d[j] + (s[i]-s[j])*c[i] + k[i]);
			}
		}
		printf("%dn", d[n]);
    }
    return 0;
}

另外也可以用sort(),自己写个类，并定义好比较用的谓词。

#include 
#include 
using namespace std;

struct kind{
    int v,k,c,l;
} a[1002];

bool compare(const kind &x, const kind &y) //!作为sort的谓词使用
{
    return x.v < y.v;
}

int main()
{
    int n=0;
    sort(a,a+n,compare);
    return 0;
}

非特殊说明，本站所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx