昨日記事が長くなることを考慮して載せなかったコード
です。
タイトルに語らせます。。。
JOI 2007 春合宿 Building
ジャッジデータどこにあるか知らないのでよくわかりませんが、まぁあり本と被ってるので解けてると思います。
#include <cstdio> #include <algorithm> using namespace std; #define INF 20000 int main() { int n; scanf("%d",&n); int a[n], dp[n]; for (int i=0; i<n; i++) scanf("%d",&a[i]); fill(dp, dp+n, INF); for (int i=0; i<n; i++) { *lower_bound(dp,dp+n,a[i])=a[i]; } printf("%d\n",lower_bound(dp,dp+n,INF)-dp); }
AOJ 0157
めんどくさいだけで内容薄いですよね(^_^;)
#include <cstdio> #include <map> #include <algorithm> using namespace std; typedef pair<int, int> P; #define F first #define S second int main() { int n, m; while (scanf("%d",&n)) { if (n==0) break; P ich[n]; for (int i=0; i<n; i++) scanf("%d%d",&ich[i].F,&ich[i].S); scanf("%d",&m); P ji[m]; for (int i=0; i<m; i++) scanf("%d%d",&ji[i].F,&ji[i].S); P mat[n+m]; for (int i=0; i<n; i++) mat[i]=ich[i]; for (int i=0; i<m; i++) mat[i+n]=ji[i]; sort(mat, mat+n+m); int dp[n+m], res=0; dp[0]=1; for (int i=1; i<n+m; i++) { dp[i]=1; for (int j=0; j<i; j++) { if (mat[j].F<mat[i].F&&mat[j].S<mat[i].S) dp[i]=max(dp[i],dp[j]+1); } res=max(res,dp[i]); } printf("%d\n",res); } }
以上でぷ