POJ2533 赤裸裸的求最长上升子序列，复杂度为n^2的模版
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[10000 + 5]; int num[10000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } int main() { int n; while(cin>>n) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) cin>>num[i]; int ans = 1; for(int i=1;i<=n;i++) dp[i] = 1; for(int i=2;i<=n;i++) { int m = 0; for(int j=1;j num[j] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; } if(ans < dp[i]) ans = dp[i]; } } cout< POJ1631，同样是赤裸裸的LIS，复杂度为nlogn的模版,n^2铁定超时 #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; int num[100000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } int main() { int t,n; cin>>t; while(t--) { clear(); cin>>n; for(int i=1;i<=n;i++) cin>>num[i]; int ans = 0; for(int i=1;i<=n;i++) { int tmp = num[i]; int left = 1; int right = ans; while(left <= right) { int mid = (left + right)/2; if(dp[mid] < tmp) left = mid + 1; else right = mid -1; } dp[left] = tmp; if(ans < left) ans++; } cout< POJ1887，最长不上升子序列，反过来做即可，注意输出格式，前导有个空格，后导两个案例之间有个空行，而且不会提醒PE 只会说WA #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; int num[100000 + 5]; void clear() { memset(dp,0,sizeof(dp));/* memset(num,0,sizeof(num));*/ } int main() { int a; int Case = 0; clear(); while(scanf("%d",&a)) { clear(); int n = 1; if(a == -1)break; num[n] = a; while(true) { scanf("%d",&a); if(a == -1)break; num[++n] = a; } for(int i=1;i<=n;i++) dp[i] = 1; int ans = 1; for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(dp[j] + 1 > dp[i] && num[i] > num[j]) dp[i] = dp[j] + 1; if(dp[i] > ans) ans = dp[i]; } } printf("Test #%d:\n",++Case); printf(" maximum possible interceptions: %d\n\n",ans); } return EXIT_SUCCESS; } POJ1609，最长不下降子序列，不过是有两个限制条件，先进行排序满足其中一条，再在这个基础上进行 LIS算法即，可注意不等号要改变，还有题目问的是最多，而序列不是给定的，所以自己要先进行排序 #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; struct Node { int x,y; }node[100000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(node,0,sizeof(node)); } bool cmp(Node x,Node y) { if(x.x == y.x) return x.y < y.y; return x.x dp[i] && node[i].x >= node[j]
POJ1631，同样是赤裸裸的LIS，复杂度为nlogn的模版,n^2铁定超时
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; int num[100000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } int main() { int t,n; cin>>t; while(t--) { clear(); cin>>n; for(int i=1;i<=n;i++) cin>>num[i]; int ans = 0; for(int i=1;i<=n;i++) { int tmp = num[i]; int left = 1; int right = ans; while(left <= right) { int mid = (left + right)/2; if(dp[mid] < tmp) left = mid + 1; else right = mid -1; } dp[left] = tmp; if(ans < left) ans++; } cout< POJ1887，最长不上升子序列，反过来做即可，注意输出格式，前导有个空格，后导两个案例之间有个空行，而且不会提醒PE 只会说WA #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; int num[100000 + 5]; void clear() { memset(dp,0,sizeof(dp));/* memset(num,0,sizeof(num));*/ } int main() { int a; int Case = 0; clear(); while(scanf("%d",&a)) { clear(); int n = 1; if(a == -1)break; num[n] = a; while(true) { scanf("%d",&a); if(a == -1)break; num[++n] = a; } for(int i=1;i<=n;i++) dp[i] = 1; int ans = 1; for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(dp[j] + 1 > dp[i] && num[i] > num[j]) dp[i] = dp[j] + 1; if(dp[i] > ans) ans = dp[i]; } } printf("Test #%d:\n",++Case); printf(" maximum possible interceptions: %d\n\n",ans); } return EXIT_SUCCESS; } POJ1609，最长不下降子序列，不过是有两个限制条件，先进行排序满足其中一条，再在这个基础上进行 LIS算法即，可注意不等号要改变，还有题目问的是最多，而序列不是给定的，所以自己要先进行排序 #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; struct Node { int x,y; }node[100000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(node,0,sizeof(node)); } bool cmp(Node x,Node y) { if(x.x == y.x) return x.y < y.y; return x.x dp[i] && node[i].x >= node[j]
POJ1887，最长不上升子序列，反过来做即可，注意输出格式，前导有个空格，后导两个案例之间有个空行，而且不会提醒PE 只会说WA
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; int num[100000 + 5]; void clear() { memset(dp,0,sizeof(dp));/* memset(num,0,sizeof(num));*/ } int main() { int a; int Case = 0; clear(); while(scanf("%d",&a)) { clear(); int n = 1; if(a == -1)break; num[n] = a; while(true) { scanf("%d",&a); if(a == -1)break; num[++n] = a; } for(int i=1;i<=n;i++) dp[i] = 1; int ans = 1; for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(dp[j] + 1 > dp[i] && num[i] > num[j]) dp[i] = dp[j] + 1; if(dp[i] > ans) ans = dp[i]; } } printf("Test #%d:\n",++Case); printf(" maximum possible interceptions: %d\n\n",ans); } return EXIT_SUCCESS; }
POJ1609，最长不下降子序列，不过是有两个限制条件，先进行排序满足其中一条，再在这个基础上进行 LIS算法即，可注意不等号要改变，还有题目问的是最多，而序列不是给定的，所以自己要先进行排序
#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int dp[100000 + 5]; struct Node { int x,y; }node[100000 + 5]; void clear() { memset(dp,0,sizeof(dp)); memset(node,0,sizeof(node)); } bool cmp(Node x,Node y) { if(x.x == y.x) return x.y < y.y; return x.x dp[i] && node[i].x >= node[j]