DP第二题,做过很多次了,这次没用记忆化搜索,而是先排序之后for循环进行动态规划.

代码如下:

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int N;struct Point {    double x, y;        void read() {        scanf("%lf %lf", &x, &y);    }}p[105];int main() {    int T, ret, ca = 0;    scanf("%d", &T);    while (T--) {        ret = 0x7fffffff+1;        scanf("%d", &N);            for (int i = 0; i < N; ++i) {            p[i].read();            }        if (N == 1) {            ret = 1;        } else {            for (int i = 0; i < N; ++i) {                for (int j = i+1; j < N; ++j) { // 枚举出所有的直线                     int cnt = 2;                    double x = p[j].x - p[i].x;                    double y = p[j].y - p[i].y;                    for (int k = j+1; k < N; ++k) {                        double a = p[k].x - p[i].x;                        double b = p[k].y - p[i].y;                        if (fabs(x*b-y*a) < 1e-6) {                            ++cnt;                        }                    }                    ret = max(ret, cnt);                }            }        }        printf("Case %d: %d\n", ++ca, ret);    }    return 0;}