DFoldingMachine(dfs)

D - Folding Machine ( dfs )

题目链接:https://codeforces.com/gym/101473/attachments

题意&＃xff1a;长度为n的原始数组a&＃xff0c;和长度为m的目标数组b&＃xff0c;问原始数组a能否通过折叠得到目标数组b。折叠方式如图。

思路&＃xff1a;n,m<&＃61;15&＃xff0c;可以暴力做&＃xff0c;每次折叠后肯定会变短&＃xff0c;所以最多折叠n-m次&＃xff0c;暴力枚举第一次折叠哪个位置&＃xff0c;第二次折叠哪个位置......用dfs来模拟。

dfs传入一个cnt表示当前数组a的长度&＃xff1b;如果当前长度等于目标长度&＃xff0c;需要判断两个数组 是否一样&＃xff0c;因为折叠的时候有左右两个方向&＃xff0c;所以判断两个数组是否一样时需要正反判断两次&＃xff1b; 如果当前长度小于目标长度&＃xff0c;直接return&＃xff0c;不用再折了&＃xff1b;如果当前长度大于目标长度&＃xff0c;需要再折叠。

如何模拟出折叠后的数组&＃xff1f;我们可以根据折叠线把数组分成两部分&＃xff0c;距离折叠线为1的就是c[1], 距离折叠先为2的就是c[2]....&＃xff0c;根据题意&＃xff0c;需要左右两部分加起来。

代码&＃xff1a;

#include using namespace std;int n,m;
int a[20],b[20];
int c[20],isp;void dfs( int cnt )
{if ( isp&＃61;&＃61;1 ) return ;if ( cnt&＃61;&＃61;m ) {int op &＃61; 1;for ( int i&＃61;1; i<&＃61;m; i&＃43;&＃43; ) {if ( b[i]!&＃61;a[i] ) {op &＃61; 0;break;}}int op2 &＃61; 1;for ( int i&＃61;m; i>&＃61;1; i-- ) {if ( b[i]!&＃61;a[m-i&＃43;1] ) {op2 &＃61; 0;break;}}if ( op&＃61;&＃61;1||op2&＃61;&＃61;1 ) isp&＃61;1;}if ( cnt&＃61;1; j-- ) {c[pos2&＃43;&＃43;] &＃43;&＃61; a[j];}for ( int i&＃61;1; i}int main()
{cin >> n;for ( int i&＃61;1; i<&＃61;n; i&＃43;&＃43; ) scanf("%d",&a[i]);cin >> m;for ( int i&＃61;1; i<&＃61;m; i&＃43;&＃43; ) scanf("%d",&b[i]);isp &＃61; 0;dfs(n);if ( isp&＃61;&＃61;1 ) cout <<"S" <}