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

快来打我* 2022-06-11 08:00 122阅读 0赞

滴，集训第十五天打卡。

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

训练也到了第九章，dp。

**uva 11400 Lighting System Design**

**![20170802184048271][]**

**题目大意：设计一个照明系统，有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**

**![20170802184642703][]**

**![20170802184654635][]**

**题目大意：在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);
    		}
    	}
    }

[20170802184048271]: /images/20220611/31d178909b6e427f87cdd1acd8c708aa.png
[20170802184642703]: /images/20220611/060681a83350486ab36d66147ad068b6.png
[20170802184654635]: /images/20220611/918e45a0565c4e0fb03960ab3aa5c018.png