{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 gwdong 的文章《ACM DP Lighting System Design&&Jin Ge Jin Qu hao》','https://www.xiaopingtou.net/article-88837.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
滴，集训第十五天打卡。
哎呀..回家了一趟落下了一大截啊...容我慢慢补起来~~
训练也到了第九章，dp。
uva 11400 Lighting System Design
题目大意：设计一个照明系统，有N种灯泡可以选择，不同种类的灯必须用不同的电源，但同一种灯泡可以共用一个电源。每种灯泡有电压V，电源费用K，每个灯泡的费用C和所需灯泡数量L。为了省钱，可以把一些灯泡换成电压更高的另一种灯泡来节省电源的钱。
思路：每种电压的灯泡，要么全换，要么全不换。先把灯泡按电压从小到大排序，那么前面的都能换后面的。设s[i]为前i种灯泡的总数量，dp[i]为灯泡1-i的最小开销，则dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*f[i].c+f[i].k)。
题目大意：设计一个照明系统，有N种灯泡可以选择，不同种类的灯必须用不同的电源，但同一种灯泡可以共用一个电源。每种灯泡有电压V，电源费用K，每个灯泡的费用C和所需灯泡数量L。为了省钱，可以把一些灯泡换成电压更高的另一种灯泡来节省电源的钱。
思路：每种电压的灯泡，要么全换，要么全不换。先把灯泡按电压从小到大排序，那么前面的都能换后面的。设s[i]为前i种灯泡的总数量，dp[i]为灯泡1-i的最小开销，则dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*f[i].c+f[i].k)。
#include
#include
#include
using namespace std;
struct sb
{
int v,k,c,l;
}f[1005];
bool cmp(sb u,sb w)
{
return u.v
UVA 12563 Jin Ge Jin Qu hao
题目大意：在KTV唱歌，剩下t秒时间，可以唱n首歌曲中的一些。使得唱的总曲目尽量多。（留下1s唱劲歌金曲）
思路：01背包问题。分别设置歌曲数目和时长两个数组。因为最多50首歌，每首歌最长180s，所以数组设置10000足够了。
#include
#include
int num[10001],times[10001];
int main()
{
int t,n,m,i,j,o=1,s,a[105];
scanf("%d",&t);
while(t--)
{
s=0;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s+=a[i];
}
printf("Case %d: ",o++);
if(s=a[i];j--)
{
if(num[j]==num[j-a[i]]+1)
{
if(times[j]