ミサイル迎撃&http://acm.nyist.net/JudgeOnline/problem.php?pid=79

1898 ワード

ダイナミック企画はとても面白いと思います.昔はあまり好きではなかったです.今はちょっと変わっています....(*^_^*)ニコニコ…このような体を作るには、主に正規の状態を探して方程式を移動します.
この問題の状態は方程式を変えます.
後ろから前へ:
if(a[i]>a[j] dp[i]=max(dp[i],dp[j]+1)
出発後:
if(a[i]ACコード:

#include<iostream>
#include<algorithm>
using namespace std;
int dp[20],a[20];
int main()
{ int Case;
   cin>>Case;
   while(Case--)
   {  int n;
      cin>>n;
      dp[n]=1;
      for(int i=0;i<n;++i)
      { dp[i]=1;
        cin>>a[i];
      }
      int maxx=-0xfffff;
      for(int i=n-1;i>0;--i)
        {    for(int j=i+1;j<=n;++j)
              if(a[i-1]>a[j-1])  dp[i]=max(dp[i],dp[j]+1);
              maxx=max(dp[i],maxx);
         }
         cout<<maxx<<endl;
      }return 0;
}

法二:

 
#include<iostream>
#include<algorithm>
using namespace std;
int dp[20],a[20];
int main()
{ int Case;
   cin>>Case;
   while(Case--)
   {  int n;
      cin>>n;
      for(int i=0;i<n;++i)
       cin>>a[i];
      int maxx=-0xfffff;
      for(int i=1;i<=n;++i)
        {      dp[i]=1;
              for(int j=1;j<i;++j)
              if(a[i-1]<a[j-1])  dp[i]=max(dp[i],dp[j]+1);
              maxx=max(dp[i],maxx);
         }
         cout<<maxx<<endl;
      }return 0;
}

法三:

 
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a, int b)
{return a>b;}
int main()
{int n;
  cin>>n;
  while(n--)
  {  int a[21];
    int b[21];
	  int m;
	  cin>>m;
	  for(int i=0;i<m;++i)
		  cin>>a[i];
	  int p=0;
    for(int i=0;i<m;++i)
	{ int* c=lower_bound(b,b+p,a[i],cmp);
	   if(c-b==p) ++p;
	    *c=a[i];
	}
	cout<<p<<endl;
  }return 0;
}

@angglar/formsソース解析の双方向結合