UVA 624 - CD

UVA 624 - CD

題目概述:

給一個最多20首的歌，每首歌有時間長度。

給一個CD的容量(時間)。求最多可以放幾分鐘。

思路:

要回朔的01背包問題。

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define maxn 100005

int w[22],v[22],dp[22][maxn],m;

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int n;

   while(cin>>m>>n)

   {

       memset(dp,0,sizeof(dp));

       for(int i=1;i<=n;++i)

           cin>>w[i],v[i]=w[i];

       for(int i=1;i<=n;++i)

           for(int j=1;j<=m;++j)

               if(j<w[i]) dp[i][j]=dp[i-1][j];

               else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);

       stack<int> st;

       for(int x=n,y=m;x!=0;--x)

       {

           if(dp[x][y]==dp[x-1][y]) continue;

           st.push(w[x]);y-=w[x];

       }

       while(st.size()) cout<<st.top()<<' ',st.pop();

       cout<<"sum:"<<dp[n][m]<<endl;

   }

}

UVA 1153 - Keep the Customer Satisfied

UVA 1153 - Keep the Customer Satisfied

題目概述:經典入門書p8-49

time&deadline題。

思路:

gready。

先對deadline做排序。接著一個一個加入pq，若發現時間超過，則拿掉最pq.top()。

最後答案為pq.size()。

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define INF 10000000000000

struct P{

   double x1,x2;

}es[100001];

bool cmp(P a,P b)

{

   return a.x1<b.x1;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   double L,D;

   int n;

   while(cin>>L>>D>>n)

   {

       for(int i=0;i<n;++i)

       {

           double x,y;cin>>x>>y;

           double dx=sqrt(D*D-y*y);

           es[i]={x-dx,x+dx};

       }

       sort(es,es+n,cmp);

       double la=INF;

       int ans=0;

       for(int i=0;i<n;++i)

       {

           P e=es[i];

           if(e.x1>la) ans++,la=e.x2;

           else la=min(la,e.x2);

       }

       if(n==0) cout<<0<<endl;

       else cout<<ans+1<<endl;

   }

}