晕死了,,总算找到了自己错在哪里了,,,
人家标程用的dp求法是记忆化搜索,,
你的那个记忆化虽然是有了,,,但是,你没有一次性将结果用好,
也就是你没有一次dp就把结果存过去,
看代码吧:
#include <stdio.h> #include <string.h> #include <iostream> #include <string> #define max(a, b) (a) > (b) ? (a) : (b) using namespace std; struct node{ int a; int b; }q[1005]; int n; int map[1005][1005]; int d[1005]; bool Judge(int i, int j) { if (q[i].a < q[j].a && q[i].b < q[j].b || q[i].a < q[j]. b && q[i].b < q[j].a) { return true; } return false; } int dp(int i) { //当然这里的ans你也可以直接用d[i]来表示, 但是如果一旦出现了多维的数组的话,,,ans就显示出他的优越性了 int &ans = d[i]; // 而这就是这道题目的精髓,就是你TLE与不TLE的差距,如果你没有这句话,就多算好多,有了就算一次, if (ans > 0) // 这是记忆化搜索的精髓,就是看看是不是已经得出d[i]; 如果得出就不必再计算了, { return ans; } ans = 1; for (int j = 0; j < n; j++) { if (map[j][i]) { ans = max(ans, dp(j) + 1); } } return ans; } int main() { int T; scanf("%d", &T); while (T--) { memset(map, 0, sizeof(map)); scanf("%d", &n); // if (n == 0) // { // printf("-1\n"); // continue; // } for (int i = 0; i < n; i++) { scanf("%d%d",&q[i].a, &q[i].b); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (Judge(i, j)) { // cout << "i = " << i << " " << "j = " << j << endl; map[i][j] = 1; } } } int t = 0; memset(d, 0, sizeof(d)); for (int i = 0; i < n; i++) { d[i] = dp(i); // printf("dp[%ds] = %d", i + 1, d[i]); // cout << endl; t = max(t, d[i]); } printf("%d\n", t); } // system("pause"); return 0; }
再修改一下下,能够按照字典序输出:
你的矩形的编号:
#include <stdio.h> #include <string.h> #include <iostream> #include <string> #define max(a, b) (a) > (b) ? (a) : (b) using namespace std; struct node{ int a; int b; }q[1005]; int n; int cnt; int map[1005][1005]; int d[1005]; int seq[1005]; bool Judge(int i, int j) { if (q[i].a < q[j].a && q[i].b < q[j].b || q[i].a < q[j]. b && q[i].b < q[j].a) { return true; } return false; } void print_ans(int i) { // printf("%d ", i + 1); for (int j = 0; j < n; j++) { if (map[j][i] == 1 && d[i] == d[j] + 1) { seq[cnt++] = j + 1; print_ans(j); break; } } } int dp(int i) { //当然这里的ans你也可以直接用d[i]来表示, 但是如果一旦出现了多维的数组的话,,,ans就显示出他的优越性了 int &ans = d[i]; // 而这就是这道题目的精髓,就是你TLE与不TLE的差距,如果你没有这句话,就多算好多,有了就算一次, if (ans > 0) // 这是记忆化搜索的精髓,就是看看是不是已经得出d[i]; 如果得出就不必再计算了, { return ans; } ans = 1; for (int j = 0; j < n; j++) { if (map[j][i]) { ans = max(ans, dp(j) + 1); } } return ans; } int main() { int T; scanf("%d", &T); while (T--) { memset(map, 0, sizeof(map)); scanf("%d", &n); // if (n == 0) // { // printf("-1\n"); // continue; // } for (int i = 0; i < n; i++) { scanf("%d%d",&q[i].a, &q[i].b); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (Judge(i, j)) { // cout << "i = " << i << " " << "j = " << j << endl; map[i][j] = 1; } } } int t = 0; int flag; memset(d, 0, sizeof(d)); int i; for (i = 0; i < n; i++) { d[i] = dp(i); // printf("dp[%ds] = %d", i + 1, d[i]); // cout << endl; // t = max(t, d[i]); if (t < d[i]) { t = d[i]; flag = i; } } cnt = 0; seq[cnt++] = flag + 1; print_ans(flag); for (int j = cnt - 1; j >= 0; j--) { printf("%d ", seq[j]); } printf("\n"); printf("%d\n", t); } system("pause"); return 0; }