企业网站怎样做外链方法,北辰集团网站建设,设计一个电商网站,怎么样宣传自己的网站不难发现这是一个LIS问题#xff0c;但是如果直接套用LIS的模版#xff0c;在数据范围到达 1 e 5 1e5 1e5 的情况下#xff0c;就只能够得到一半的分数#xff0c;所以我们需要对其进行优化。
首先给出暴力的代码#xff1a;
#includeiostream
using namespace… 不难发现这是一个LIS问题但是如果直接套用LIS的模版在数据范围到达 1 e 5 1e5 1e5 的情况下就只能够得到一半的分数所以我们需要对其进行优化。
首先给出暴力的代码
#includeiostream
using namespace std;
const int N 1e510;string a[N]; //为了方便比较数的首尾直接用string类型存
int f[N];int main(){int n;cin n;for(int i 1;i n;i)cin a[i];for(int i 1;i n;i){f[i] 1;for(int j 1;j i;j){if(a[i][0] a[j][a[j].length() - 1])f[i] max(f[i],f[j] 1);}}int res 0;for(int i 1;i n;i)res max(res,f[i]);cout n - res;return 0;
}那么如何优化注意到暴力程序只有一个地方达到了两层的循环所以我们只要优化掉一层循环即可。 那么如何优化以下代码
for(int j 1;j i;j){if(a[i][0] a[j][a[j].length() - 1])f[i] max(f[i],f[j] 1);
}此处代码写出来是为了枚举比较首尾那么如果我们能够直接定位和a[i]的首部相同尾部的子序列的长度不就不需要判断了吗。
所以使用一个数组来存尾部是 1 1 1 ~ 9 9 9 中某一个数结尾的接龙子序列的最长长度在状态转移时直接省掉了判断的步骤。
优化代码
#includeiostream
#includemap
using namespace std;
const int N 1e5 10;string a[N];
mapchar,intm;
int f[N];int main() {int n; cin n;for (int i 1; i n; i)cin a[i];for (int i 1; i n; i) {f[i] 1;f[i] max(f[i],m[a[i][0]] 1);m[a[i][a[i].length() - 1]] max(f[i],m[a[i][a[i].length() - 1]]);//这里必须取max因为f[i]不一定就更大}int res 0;for(int i 1;i n;i)res max(res,f[i]);cout n - res;return 0;
}
