- NightElf
- 2014-07-11 14:39:45 @
#include <iostream>
using namespace std;
const int inf=10000000;
struct node{
int day,res;
};
int n,k;
int cnt;
int a[3050];
node f[3050];
int min(int a,int b)
{
return a>b?a:b;
}
int main()
{
cin>>n>>k;
int i,j;
for(i=1;i<=n;i++)
{
cin>>j;
if(j>=120)continue;
cnt++;
a[i]=j;
}
if(cnt<k)
{
cout<<"You can't do it."<<endl;
return 0;
}
int midt,midd;
for(i=1;i<=n;i++)
{
f[i]=inf;
if(a[i]>=120)
{
continue;
}
for(j=i;j>=1;j--)
{
if(f[j-1].day==inf)continue;
if(f[j-1].res>a[i])
{
midt=f[j-1].res-a[i];
midd=f[j-1].day;
}
else
{
midt=120-a[i];
midd=f[j-1].day+1;
}
if(midd<f[j].day || (midd==f[j].day && midt>f[j].res))
{
f[j].res=midt;
f[j].day=midd;
}
}
}
cout<<f[k].day<<endl;
return 0;
}
1 条评论
-
mli LV 3 @ 2016-03-21 22:17:42
在给f[i]赋初值那不对,f[i]是node型,inf是int型
- 1