商丘做网站用什么程序,做网站的图片Pc端和手机端的区别,爱写字 wordpress,淘宝网页设计与制作教程哈密顿路径问题#xff1a;
一般设 表示 状态下#xff0c;为最后一个最值情况 。
一般有两种稍微不同的写法#xff0c;单纯就是写法不同#xff0c;思路方法都相同。
第一个例题为第一种转移方法#xff0c;有当前转移后面。
后面的都是由前面转移目前。
G. Shuff…哈密顿路径问题
一般设 表示 状态下为最后一个最值情况 。
一般有两种稍微不同的写法单纯就是写法不同思路方法都相同。
第一个例题为第一种转移方法有当前转移后面。
后面的都是由前面转移目前。
G. Shuffling Songs
题意就是要你删除最少的歌曲使其播放精彩,每对相邻的歌曲要么作者相同要么流派相同(或两者皆有)即为精彩。
思路观察数据范围可以发现2的16次方枚举类似哈密顿路劲问题转移即可
string g[N], s[N];
int n;
void solve()
{cin n;for (int i 0; i n; i)cin g[i] s[i];vectorint e(n, 0);for (int i 0; i n; i){for (int j 0; j n; j){if (g[i] g[j] || s[i] s[j])e[i] | (1 j);}}vectorvectorint f(1 n, vectorint(n, 0));for (int i 0; i n; i)f[1 i][i] 1;for (int i 0; i (1 n); i){for (int j 0; j n; j) // 最后一个点是谁{if (!f[i][j])continue;for (int k 0; k n; k){if (i k 1) // 加进去一个点continue;if ((e[j] k) 1){f[i | (1 k)][k] 1;}}}}int ans 0;for (int i 0; i (1 n); i){for (int j 0; j n; j)if (f[i][j])ans max(ans, __builtin_popcount(i));}cout n - ans endl;
}AcWing 731. 毕业旅行问题
同理也是哈密顿路径问题 int g[M][M];
int f[1 20][20];
void solve()
{int n;cin n;for (int i 0; i n; i)for (int j 0; j n; j)cin g[i][j];memset(f, inf, sizeof f);f[1][0] 0;for (int i 0; i (1 n); i){for (int j 0; j n; j){if (i j 1){for (int k 0; k n; k){if (i - (1 j) k 1){f[i][j] min(f[i][j], f[i - (1 j)][k] g[k][j]);}}}}}int ans 1e18;for (int i 1; i n; i)ans min(ans, f[(1 n) - 1][i] g[i][0]);cout ans endl;
} 91. 最短Hamilton路径 int f[1 20][21];
int g[M][M];
void solve()
{int n;cin n;for (int i 0; i n; i){for (int j 0; j n; j)cin g[i][j];}memset(f, 0x7f, sizeof f);f[1][0] 0;for (int i 0; i (1 n); i){for (int j 0; j n; j){if (i j 1){for (int k 0; k n; k){if (i - (1 j) k 1){f[i][j] min(f[i - (1 j)][k] g[k][j], f[i][j]);}}}}}cout f[(1 n) - 1][n - 1] endl;
}
