全国做网站的公司有哪些,做a 需要制作网站,深圳网站建设要多少钱,新网站 seo出自一次很失败的开学测试 LIS自然会做 可以参见#xff1a;https://blog.csdn.net/Radium_1209/article/details/79704234 由于对于LIS的nlogn算法不熟悉#xff0c;导致错误理解#xff0c;记录的路径出现了问题#xff0c;其中还用了n^2的算法记录路径#xff08;好理解… 出自一次很失败的开学测试 LIS自然会做 可以参见https://blog.csdn.net/Radium_1209/article/details/79704234 由于对于LIS的nlogn算法不熟悉导致错误理解记录的路径出现了问题其中还用了n^2的算法记录路径好理解但是不出所料T了。 正确的方法应该是由于nlogn算法中dp[i]存的是长度为i的最后一位数字并不是路径我们可以用一个path数组来标记每一个数字位于的位置然后通过dfs倒着来找最后结果长度的最后一个或者不用dfs直接找也行。 例题(UVA481) Write a program that will select the longest strictly increasing subsequence from a sequence of integers. Input The input file will contain a sequence of integers (positive, negative, and/or zero). Each line of the input file will contain one integer. Output The output for this program will be a line indicating the length of the longest subsequence, a newline, a dash character (-), a newline, and then the subsequence itself printed with one integer per line. If the input contains more than one longest subsequence, the output file should print the one that occurs last in the input file. Notice that the second 8 was not included -- the subsequence must be strictly increasing. Sample Input -7
10
9
2
3
8
8
1 Sample Output 4
-
-7
2
3
8题意求LIS并输出路径最后一个 dfs版 #include cstdio
#include iostream
using namespace std;int n1,a[1000005];
int dp[1000005];
int path[1000005];void dfs(int i,int x)
{if (i1 || x0)return;while(path[i]!x)i--;dfs(i,x-1);printf(%d\n,a[i]);
}int main()
{while(~scanf(%d,a[n])){n;}n--;int len1;dp[1]a[1]; path[1]1;for (int i2;in;i){if (a[i]dp[len]){dp[len]a[i];path[i]len;}else{int poslower_bound(dp1,dplen1,a[i])-dp;dp[pos]a[i];path[i]pos;}}printf(%d\n-\n,len);dfs(n,len);return 0;
}非dfs版 #include cstdio
#include iostream
using namespace std;int n1,a[1000005];
int dp[1000005];
int path[1000005];
int ans[1000005];int main()
{while(~scanf(%d,a[n])){n;}n--;int len1;dp[1]a[1]; path[1]1;for (int i2;in;i){if (a[i]dp[len]){dp[len]a[i];path[i]len;}else{int poslower_bound(dp1,dplen1,a[i])-dp;dp[pos]a[i];path[i]pos;}}printf(%d\n-\n,len);int tempn;int llen;while(l1){int i;for(itemp;i1;i--){if (path[i]l){ans[l]a[i];l--; tempi;break;}}if (i0)break;}for (int i1;ilen;i)printf(%d\n,ans[i]);return 0;
} n^2版本T了正确性未知 #include cstdio
#include iostream
using namespace std;int n1,a[1000005];
int dp[1000005];
int path[1000005];
int ans[1000005];int main()
{while(~scanf(%d,a[n])){n;}n--;int len0;for (int i1;in;i){dp[i]1;for (int j1;ji;j)if (a[j]a[i]){if (dp[i]dp[j]1){dp[i]dp[j]1;path[dp[i]]j;}}if (dp[i]len){lendp[i];ans[len]a[i];for (int ilen;i2;i--)ans[i-1]a[path[i]];}}printf(%d\n-\n,len);for (int i1;ilen;i)printf(%d\n,ans[i]);return 0;
} 转载于:https://www.cnblogs.com/Radium1209/p/10415345.html
