ZOJ 1025 Wooden Sticks（贪心 基础题）
分类：DP
题目链接
题意：
机器加工n个木条，每个木条有一个长度和重量。加工第一根木条需要1分钟的准备时间，接下来如果后一根木条的长度和质量都大于等于前一根木条，则不需要准备时间，否则需要1分钟的准备时间，，求加工完所有木条最少时间。
比如有5根木条，长度和重量分别是(4,9), (5,2), (2,1), (3,5), (1,4),则需要2分钟就可加工第1分钟加工(1,4), (3,5), (4,9)；第2分钟加工(2,1), (5,2)；
思路：将木条按长度从小到大排序，dp[i]记录第i根木条是在什么时刻被加工的（初始化为1）；
如果第i根木条比同一时间加工的木条长度都要短，质量都要轻的话，那么它的dp就不变，否则加1.
代码如下：
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;const int N = 5005;typedef long long ll;int n;int dp[N];struct node{int l, w;bool operator< (const node &rhs) const{if(l != rhs.l) return l < rhs.l;return w <= rhs.w;}}stick[N];int main(){int t;scanf("%d", &t);while(t–){scanf("%d", &n);for(int i = 0; i < n; i++){scanf("%d%d", &stick[i].l, &stick[i].w);}sort(stick, stick + n);dp[0] = 1;int ans = 0;for(int i = 1; i < n; i++){dp[i] = 1;for(int j = 0; j < i; j++){if(stick[j].w > stick[i].w && dp[i] == dp[j]){dp[i] = dp[j] + 1;}}}for(int i = 0; i < n; i++){ans = max(ans, dp[i]);}printf("%d\n", ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇ZOJ 1093 Monkey and Banana
顶0踩0
飞机一阵抖动，我终于说出了最后一句再见。
