此題使用動態(tài)規(guī)劃。首先做一些預處理：排序。按體重由小到大排序，相同體重的按IQ遞減排序。動態(tài)規(guī)劃的狀態(tài)轉移方程為d[i]=max{d[j]+1|j<i,a[j].weight<a[i].weight,a[j].iq>a[i].iq}。
以下是我的代碼：
#include<stdio.h>
//#define LOCAL
typedef struct
{
long id,weight,iq;
}type;
const long maxn=1007;
long n,ans,pos,d[maxn],f[maxn],tmp[maxn];
type a[maxn];
void Qsort(long begin,long end)
{
long i=begin,j=end,mid1=a[(begin+end)/2].weight,mid2=a[(begin+end)/2].iq;
type t;
do{
while(a[i].weight<mid1||(a[i].weight==mid1&&a[i].iq>mid2)) i++;
while(a[j].weight>mid1||(a[j].weight==mid1&&a[j].iq<mid2)) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(i<end) Qsort(i,end);
if(j>begin) Qsort(begin,j);
}
int main()
{
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
n=0;
while(scanf("%ld%ld",&a[n+1].weight,&a[n+1].iq)==2)
{
n++;
a[n].id=n;
}
// Input
Qsort(1,n);
// Qsort
for(long i=1;i<=n;i++)
{
d[i]=1;
f[i]=0;
}
// Init
for(long i=1;i<=n;i++)
for(long j=1;j<i;j++)
if(a[i].weight>a[j].weight&&a[i].iq<a[j].iq&&d[i]<d[j]+1)
{
d[i]=d[j]+1;
f[i]=j;
}
// DP
ans=0;pos=0;
for(long i=1;i<=n;i++)
if(d[i]>ans)
{
ans=d[i];
pos=i;
}
tmp[1]=a[pos].id;
for(long i=2;i<=ans;i++,pos=f[pos])
tmp[i]=a[f[pos]].id;
printf("%ld\n",ans);
for(long i=ans;i>=1;i--)
printf("%ld\n",tmp[i]);
// Output
return 0;
}
posted on 2010-02-08 14:19
lee1r 閱讀(720)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃