[UVA][dp] 10421 - Critical Wave
Problem C
Critical
Wave
Input: standard input
Output: standard output
Time Limit: 10 seconds
The task is simple. Through some critical points in 2D, you are to draw a wave like curve. Your goal is to include as many points as possible.
- There will be an imaginary line y = a, which we call the major axis for the curve.
- All the points on the curve should have different x coordinates. Their y coordinates should be of form a-1 or a+1.
Two consecutive points on the curve should have a difference of 2 in their y coordinate
Input
There will be no more than 222 test cases. Each test case starts with an integer N, the number of points in the test case. In the next N lines, there will be N pair of integers giving the x and y coordinate of the points. There will be no more than 1000 points in each test case. All coordinates are integers -- they'd fit in an signed 2 byte integer data type.
Output
For each test case print a number -- the maximum number of critical points that can be included in a curve drawn from the given points.
Sample Input
100 11 01 -12 -23 13 -13 -24 14 -1
5 –1
100 11 01 -12 -23 13 -13 -24 14 -1
5 –1
Sample Output
4
4
Problem-setter: Monirul Hasan Tomal
“If you don’t consider your life as a journey you will advance nowhere and life will appear to you as an endless and hopeless track.”
這裡用最樸素的 O(n^2) 計算 LIS。
題目描述很簡單，找一條 y = a，並且找到一組數列符合由左而右 x 座標都不同。
且上下上下 y 值差 2 的方式擺動。
由於沒有給定 a 值，因此使用 dp 去計算。狀態分成兩種，
以它為結尾時，它前一次是上、它前一次是下。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct Pt {
int x, y;
Pt(int a=0, int b=0) :
x(a), y(b) {}
bool operator<(const Pt &a) const {
if(a.x != x)
return x < a.x;
return y < a.y;
}
};
int main() {
int n;
int i, j, k;
Pt D[1005];
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d %d", &D[i].x, &D[i].y);
sort(D, D+n);
int ret = 0;
int dp[1005][2];
for(i = 0; i < n; i++) {
dp[i][0] = dp[i][1] = 1;
for(j = i-1; j >= 0; j--) {
if(D[i].x == D[j].x)
continue;
if(D[i].y == D[j].y+2)
dp[i][0] = max(dp[i][0], dp[j][1]+1);
if(D[i].y == D[j].y-2)
dp[i][1] = max(dp[i][1], dp[j][0]+1);
}
ret = max(ret, dp[i][0]);
ret = max(ret, dp[i][1]);
}
printf("%d\n", ret);
}
return 0;
}