第一题;http://acm.hdu.edu.cn/showproblem.php?pid=1257
贪心与dp傻傻分不清楚,把每一个系统的最小值存起来比较
#include<cstdio>
using namespace std;
int a[],b[];
int main()
{
int n,i,j;
while (~scanf("%d",&n))
{
int ans=;
b[]=-;
for (i=;i<n;i++)
{
scanf("%d",&a[i]);
for (j=;j<=ans;j++)
{
if (a[i]<=b[j])
{
b[j]=a[i];
break;
}
if (j==ans)
{
ans++;
b[ans]=a[i];
break;
}
}
}
printf("%d\n",ans);
}
return ;
}
第二题;http://acm.hdu.edu.cn/showproblem.php?pid=1789
t组测试数据,一个人要做n完份作业,第一行是每个作业规定的最迟的提交的时间,第二行是每个作业超过规定时间提交要扣除的分数,求扣除的最小分数
将扣得分数排序,先考虑影响最大的,然后填充时间
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point {
int time,val;
bool operator <(const point & q) const
{
//if (val==q.val) return q.time>time;
return q.val<val;
}
};
point yj[];
int vis[];
int main()
{
int t,i,j,n;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i=;i<=n;i++)
scanf("%d",&yj[i].time);
for (i=;i<=n;i++)
scanf("%d",&yj[i].val);
sort(yj+,yj+n+);
memset(vis,,sizeof(vis));
int sum=;
for (i=;i<=n;i++)
{
for (j=yj[i].time;j>;j--)
{
if (vis[j]==)
{
vis[j]=;
break;
}
}
if (j==)
sum+=yj[i].val;
}
printf("%d\n",sum);
}
return ;
}