做网站大作业的心得体会,软文推广渠道,深圳做app网站制作,竞价推广方案问题#xff1a;
如下图所示。图中有两行正整数#xff0c;每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同#xff0c;这样就可以在这两个正整数之间划一条线#xff0c;并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。 请编写完整程序#xf…问题
如下图所示。图中有两行正整数每行中有若干个正整数。如果第一行的某个数r与第二行的某个数相同这样就可以在这两个正整数之间划一条线并称之为r-匹配线段。下图中存在3-匹配线段和2-匹配线段。 请编写完整程序求最大的匹配线段数量并使得这些匹配线段满足如下条件
每一个a-匹配线段必须与另一个b-匹配线段相交且a不等于b.任何两个匹配线段不能从同一个整数出发。如下图中3-匹配线段是不合法的匹配线段。 不满足上述两个条件的匹配线段则不能称之为匹配线段不计入匹配线段的数量。例如有两行整数分别如下则该例中其匹配线段的数量为6.
1 3 1 3 1 3
3 1 3 1 3 1
下面的匹配线段数量则为0。因为虽然最多可划4条匹配线段但不满足这其中2条匹配线段相交且a-匹配线段不等于b匹配线段的条件因此其匹配线段的数量为0.
1 1 3 3
1 1 3 3 思路
回溯法。
第n层顺序考虑第1行的第n个正整数与第2行的某个正整数进行匹配匹配后需要在一个一维向量中标记代表下次不可以参与匹配。
当达到深度时分支被目标函数截断进行匹配线段的计算也要找匹配找到一定记得退出循环那么将匹配线段数目与最优值作比较更新最优值。
难点匹配线段的计算函数匹配对的存储。 代码
#includebits/stdc.h
using namespace std;typedef pairint, int PII;
int n;
int first[110];
int second[110];
int sign[110];
int best;int cal(int cnt, PII duple[])
{int result 0;int sign[cnt1] {0};for(int i 1; i cnt; i){if(sign[i]) continue;for(int j 1; j cnt; j){if(first[duple[i].first] first[duple[j].first]) continue;if((duple[i].first - duple[j].first) * (duple[i].second - duple[j].second) 0){sign[i] 1, result 1;if(!sign[j]) sign[j] 1, result 1;break;}}}return result;
}
void dfs(int k, int cnt, PII duple[])
{if(k n){int this_time cal(cnt, duple);if(this_time best) best this_time;}for(int i 1; i n; i){if(second[i] ! first[k]) continue;if(sign[i]) continue;sign[i] 1;duple[cnt1] {k, i};dfs(k1, cnt1, duple);duple[cnt1] {}; sign[i] 0;}
}
int main()
{cin n;for(int i 1; i n; i){cin first[i];}for(int i 1; i n; i){cin second[i];}PII duple[110];dfs(1, 0, duple);cout best endl;return 0;
}
