ACM DP Lighting System Design&&Jin Ge Jin Qu hao

滴，集训第十五天打卡。

哎呀..回家了一趟落下了一大截啊...容我慢慢补起来~~

训练也到了第九章，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)。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct sb
{
	int v,k,c,l;
}f[1005];
bool cmp(sb u,sb w)
{
	return u.v<w.v;
}
int main()
{
	int n,i,j,dp[1005],s[1005],ss;
	while(scanf("%d",&n))
	{
		if(n==0)break;
		for(i=1;i<=n;i++)
		scanf("%d %d %d %d",&f[i].v,&f[i].k,&f[i].c,&f[i].l);
		sort(f+1,f+n+1,cmp);
		ss=0;
	 	memset(dp,0x7f7f7f7f,sizeof(dp)); 
	 	dp[0]=0;s[0]=0;
		for(i=1;i<=n;i++)
		{
			ss+=f[i].l;
			s[i]=ss;
			for(j=0;j<i;j++)
			{
				dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*f[i].c+f[i].k);
				//printf("%d**\n",dp[j]+(s[i]-s[j])*f[i].c+f[i].k);
			}
		}
		printf("%d\n",dp[n]);
	}
}

UVA 12563 Jin Ge Jin Qu hao

题目大意：在KTV唱歌，剩下t秒时间，可以唱n首歌曲中的一些。使得唱的总曲目尽量多。（留下1s唱劲歌金曲）

思路：01背包问题。分别设置歌曲数目和时长两个数组。因为最多50首歌，每首歌最长180s，所以数组设置10000足够了。

#include <stdio.h>
#include <string.h>
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<m)
		printf("%d %d\n",n+1,s+678);
		else
		{
			memset(num,0,sizeof(num));
			memset(times,0,sizeof(times));
			for(i=1;i<=n;i++)
			{
				for(j=m-1;j>=a[i];j--)
				{
					if(num[j]==num[j-a[i]]+1)
					{
						if(times[j]<times[j-a[i]]+a[i])
						times[j]=times[j-a[i]]+a[i];
					}
					else if(num[j]<num[j-a[i]]+1)
					{
						num[j]=num[j-a[i]]+1;
						times[j]=times[j-a[i]]+a[i];
					}
				}
			}
			printf("%d %d\n",num[m-1]+1,times[m-1]+678);
		}
	}
}