UVA11400照明系统设计&& POJ1260Peals(DP)

紫书P275: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105116#problem/A

POJ http://poj.org/problem?id=1260

两个题一种类型:

UVA11400 : n个灯泡可以选择,每个灯泡有四个属性,v需要电压,k电源费用,c每个灯泡的费用和所需灯泡的数量L,每种类型的灯泡必须配一种类型的电源费用,低电压可以选择换用高电压的灯泡,计算最小费用

首先不能跨电压(1和3, 2),之前一直想不明白,其实可以这么想,1,2,3,电压是递增的,如果1和3在一起,为什么1选择3,不选择2呢?

(1)假设2和3电源费用是相同的,而3的灯泡比2的便宜,所以1选择3会有最小费用,既然如此,2也得选择3才有最优解

(2)假设2和3灯泡的价值是一样的,而3的电源费用比较低,所以1选3,同样,2选3才会有会有最优解

所以不会跨电压!

s[i]表示前i种灯泡的数量,dp[i]前i种灯泡的最小费用,dp[i] = min(dp[j] + (sum[i] - sum[j]) * c[i] + k[i])   0 <= j < i 表示前j个用最优策略买,后面的以i的价格买

POJ 1260:珍珠的数量a和价格p,每买一种需要多买10个,低等的可以高价买,一样的意思, dp[i] = min(dp[j] + (sum[i]- sum[j] + 10) * p[i])

 #include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = + ;
const int INF = 0x3f3f3f3f;
struct Lamp
{
int v,k,c,l;
};
Lamp lamp[MAX];
int sum[MAX],dp[MAX];
int cmp(Lamp x, Lamp y)
{
return x.v < y.v;
}
int main()
{
int n;
while(scanf("%d", &n) != EOF && n)
{
for(int i = ; i <= n; i++)
{
scanf("%d%d%d%d", &lamp[i].v, &lamp[i].k, &lamp[i].c, &lamp[i].l);
}
sort(lamp + , lamp + n + , cmp);
memset(sum, , sizeof(sum));
memset(dp, , sizeof(dp));
sum[] = lamp[].l;
for(int i = ; i <= n; i++)
sum[i] = sum[i - ] + lamp[i].l;
dp[] = lamp[].c * lamp[].l + lamp[].k;
for(int i = ; i <= n; i++)
{
int minn = INF;
for(int j = ; j < i; j++)
{
minn = min(minn, dp[j] + (sum[i] - sum[j]) * lamp[i].c + lamp[i].k);
}
dp[i] = minn;
}
printf("%d\n", dp[n]);
}
return ;
}

UVA11400

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = + ;
struct Peal
{
int a,p;
};
Peal peal[N];
int c,dp[N],sum[N];
int cmp(Peal x, Peal y)
{
return x.p < y.p;
}
int main()
{
int test;
scanf("%d", &test);
while(test--)
{
scanf("%d", &c);
for(int i = ; i <= c; i++)
{
scanf("%d%d", &peal[i].a, &peal[i].p);
}
//sort(peal + 1, peal + c + 1, cmp); 加排序就WA
memset(sum, , sizeof(sum));
memset(dp, , sizeof(dp));
for(int i = ; i <= c; i++)
{
sum[i] = sum[i - ] + peal[i].a;
}
dp[] = ( peal[].a + ) * peal[].p;
for(int i = ; i <= c; i++)
{
int minn = INF;
for(int j = ; j < i; j++)
{
minn = min(minn, dp[j] + (sum[i] - sum[j] + ) * peal[i].p);
}
dp[i] = minn;
}
printf("%d\n", dp[c]);
}
return ;
}

poj1260

上一篇:JavaWEB域对象


下一篇:truncate和 delete的区别: