小白dp uva 10154 – Weights and Measures （貪心+dp ）

Problem F: Weights and Measures

I know, up on top you are seeing great sights,
But down at the bottom, we, too, should have rights.
We turtles can’t stand it. Our shells will all crack!
Besides, we need food. We are starving!” groaned Mack.

The Problem

Mack, in an effort to avoid being cracked, has enlisted your advice as to the order in which turtles should be dispatched to form Yertle’s throne. Each of the five thousand, six hundred and seven turtles ordered
by Yertle has a different weight and strength. Your task is to build the largest stack of turtles possible.

Standard input consists of several lines, each containing a pair of integers separated by one or more space characters, specifying the weight and strength of a turtle. The weight of the turtle is in grams. The strength,
also in grams, is the turtle’s overall carrying capacity, including its own weight. That is, a turtle weighing 300g with a strength of 1000g could carry 700g of turtles on its back. There are at most 5,607 turtles.

Your output is a single integer indicating the maximum number of turtles that can be stacked without exceeding the strength of any one.

Sample Input

Sample Output

題意：
給出n個烏龜的重量w和承載量s，讓你用其中一些烏龜堆出一個高度最大的stack來。
n<5607，w、s范圍未給。

思路：
貪心分析知s-w小的需在前面，先按s-w排序，然後dp。
dp[i][j] — 第i個烏龜堆出第j層所需的最小重量。
那麼有 dp[i][j]=min(dp[i-1][j],dp[i-1][j-1]+w[i]); 前提 i 能承載

感想：
開始想狀態總想著有一維與重量相關什麼的，每到一個狀態既要保證高度大，又要保證重量小，感覺好困難的樣子，思路受阻，還是看瞭題解怎樣找的狀態，狀態知道後立馬就知道怎麼做瞭 = =。
其實題目給出的數據范圍、或未給的來推測能暗示你怎樣建狀態的，朝不看題解繼續努力！

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 5700
#define MAXN 100005
#define mod 1000000007
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 0.000001
typedef long long ll;
using namespace std;

int n,m,ans,cnt,tot,flag;
int dp[maxn];
struct Node
{
    int w,s;
}pp[maxn];

void solve()
{
    int i,j,t;
    ans=0;
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(i=1;i=1;j--)
        {
            if(pp[i].s-pp[i].w>=dp[j-1])
            {
                dp[j]=min(dp[j],dp[j-1]+pp[i].w);
                if(dp[j]<INF) ans=max(ans,j);
            }
        }
    }
}
bool cmp(Node xx,Node yy)
{
    return xx.s-xx.w<yy.s-yy.w;
}
int main()
{
    int i,j,u,v,t=0;
    while(~scanf("%d%d",&u,&v))
    {
        t++;
        pp[t].w=u;
        pp[t].s=v;
    }
    n=t;
    sort(pp+1,pp+t+1,cmp);
    solve();
    printf("%d\n",ans);
    return 0;
}
/*
300 1000
1000 1200
200 600
100 101
*/

Problem F: Weights and Measures

The Problem

Sample Input

Related posts:

發佈留言 取消回覆

發佈留言取消回覆