Vijos p1303導彈攔截（LIS+貪心)
來源：程序員人生 發布時間：2014-11-13 08:21:07 閱讀次數：3542次
傳送門：https://vijos.org/p/1303
背景
實中編程者同盟為了培養技術高深的后備人材，必須從基礎題開始訓練。
描寫
某國為了防御敵國的導彈攻擊，研發出1種導彈攔截系統。但是這類導彈攔截系統有1個缺點：雖然它的第1發炮彈能夠到達任意的高度，但是以后每發炮彈都不能高于前1發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在實驗階段，所以只有1套系統，因此有可能不能攔截所有的導彈。
格式
輸入格式
輸入數據只有1行，該行包括若干個數據，之間用半角逗號隔開，表示導彈順次飛來的高度（導彈最多有 20 枚，其高度為不大于 30000 的正整數）。
輸出格式
輸出數據只有1行，該行包括兩個數據，之間用半角逗號隔開。第1個數據表示這套系統最多能攔截的導彈數；第2個數據表示若要攔截所有導彈最少要再添加多少套這樣的系統。
樣例1
樣例輸入1
389,207,155,300,299,170,158,65
樣例輸出1
6,1
思路：LIS,寫成這樣也是醉了，姿式不夠啊，水題1A。第2問就是貪心了，每次選擇已有的最小高度，最大的都不夠的時候，就添加系統。
代碼：
/*
author：Ac_sorry
problem:導彈攔截
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<climits>
#define INF INT_MAX
using namespace std;
int a[50];
int dp[50];
int main()
{
int cnt=0;
scanf("%d",&a[cnt++]);
while(scanf(",%d",&a[cnt])==1)
{
cnt++;
}
//printf("%d----
",cnt);
memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=1;i<cnt;i++)
{
int maxx=0;
for(int j=0;j<i;j++)
{
if(a[i]<a[j]&&dp[j]>maxx)
maxx=dp[j];
}
dp[i]=maxx+1;
}
vector<int> ans;
for(int i=0;i<cnt;i++)
{
int minn=300000,pos=⑴;
for(int j=0;j<ans.size();j++)
{
if(ans[j]<minn&&ans[j]>=a[i])
{
minn=ans[j];
pos=j;
}
}
if(pos==⑴)
ans.push_back(a[i]);
else
ans[pos]=a[i];
}
int maxx=0;
for(int i=0;i<cnt;i++)
{
maxx=max(dp[i],maxx);
}
printf("%d,%d
",maxx,ans.size()⑴);
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
