21年下学期第六周周练（动态规划，搜索，英语专题）

英语专题）"/>

21年下学期第六周周练（动态规划，搜索，英语专题）

B - Multiplication Puzzle

问题分析：

我一开始的思路是暴力搜索，当然是不可行的，题目数据规模到了100，即便我使用了一些减枝，整体的时间复杂度还是一个阶乘的级别，太恐怖了。
下一个思路是区间动规，动规写的有点少了，需要狂补啊！！！
步骤一：确定状态
步骤二：确定状态转移方程
步骤三：确定边界情况和初始条件
步骤四：确定计算顺序
选择以dp[I][J]作为状态，意味着从第I个数到第J个数的最小sum值；
状态转移方程为：

for(int k = i + 1;k <= j - 1;k++){dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]);}

先将dp[I][J]初始化为INT_MAX就行了
我们的计算顺序跟以前有点不一样，不是简单的自上而下、自左向右，而是以区间作为基本元素，从小区间推广到大区间，并且要保证每个小区间均满足条件后才会继续往下推广。

解决代码：

#include<iostream>
using namespace std;
int a[105];
int dp[105][105];//代表从i到j的最小目标值 
int main(){int n;cin>>n;for(int i = 1;i <= n;i++)cin>>a[i];for(int l = 2;l <= n - 1;l++){//区间的大小 for(int i = 1;i + l <= n;i++){int j = i + l;dp[i][j] = INT_MAX;for(int k = i + 1;k <= j - 1;k++){dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]);}}}cout<<dp[1][n];return 0;
}

C - Zipper

问题分析：

判断是否可以由字符串A跟B组合成字符串C，同时不改变A，B的顺序。
我第一个思路还是DFS，试了好几遍，太容易超时了，但是摸索了一遍又一遍，发现了几个条件，只要满足，还是可以AC的，嘿嘿嘿，在超时跟AC之间疯狂试探。
第二个思路是动态规划，也是这道题的常规解法：
s[i][j]代表由一串i个字符与二串j个字符能否组成三串中长度为（i+j-1）的字符串；
之后处理边界条件，这道题有点不严谨的情况，哪怕边界条件没处理好，也不影响AC，先令s[0][0]为1，再分别处理s[0][i]跟s[i][0]。
递推公式为：

for(int i=1;i<=x;i++){for(int j=1;j<=y;j++){s[i][j]=((a[0][i-1]==a[2][i+j-1] && s[i-1][j]) || (a[1][j-1]==a[2][i+j-1] && s[i][j-1]));}}

解决代码：

//DFS
#include<bits/stdc++.h>
using namespace std;
struct node{int i;//一串下标 int j;//二串下标 int k;//三串下标 
};
int n;//组数 
int mark;//标记是否找到 
int main(){cin>>n;for(int z=1;z<=n;z++){string a[3];node tmp;mark=0;for(int i=0;i<3;i++)cin>>a[i];stack<node>s;int i,j,k;i=j=k=0;tmp.i=i;tmp.j=j;tmp.k=k;s.push(tmp);cout<<"Data set "<<z<<": ";if(a[0].length()+a[1].length()!=a[2].length());else if(a[0][a[0].length()-1]!=a[2][a[2].length()-1]&&a[1][a[1].length()-1]!=a[2][a[2].length()-1]);else while(!s.empty()){tmp=s.top();s.pop();if(tmp.k==a[2].length()){mark=1;cout<<"yes"<<endl;break;}if(a[0][tmp.i]==a[2][tmp.k]){node ss;ss.i=tmp.i+1;ss.j=tmp.j;ss.k=tmp.k+1;s.push(ss);}if(a[1][tmp.j]==a[2][tmp.k]){node ss;ss.i=tmp.i;ss.j=tmp.j+1;ss.k=tmp.k+1;s.push(ss);}}if(mark==0)cout<<"no"<<endl;}return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;//组数 
int x,y;//一串，二串的长度 
int s[205][205];//s[i][j]代表由一串i个字符与二串j个字符能否组成三串中长度为（i+j-1） 
int main(){cin>>n;for(int z=1;z<=n;z++){string a[3];memset(s,0,sizeof(s));for(int i=0;i<3;i++)cin>>a[i];x=a[0].length();y=a[1].length();cout<<"Data set "<<z<<": ";s[0][0]=1;for(int i=1;i<=x;i++)s[i][0]=(a[0][i-1]==a[2][i-1]&&s[i-1][0]);for(int i=1;i<=y;i++)s[0][i]=(a[1][i-1]==a[2][i-1]&&s[0][i-1]);for(int i=1;i<=x;i++){for(int j=1;j<=y;j++){s[i][j]=((a[0][i-1]==a[2][i+j-1] && s[i-1][j]) || (a[1][j-1]==a[2][i+j-1] && s[i][j-1]));}}(s[x][y]==0)?cout<<"no"<<endl:cout<<"yes"<<endl;}return 0;
}

D - Incomplete chess boards

问题分析：

题意是在一个8 * 8的棋盘上，挖去两个点，之后判断剩余的格子能否仅使用1 * 2的板子来覆盖。
我一开始没什么思路，想过用DFS来模拟，但存在两个问题，首先是搜索起点的确认，因为会从中挖去两个点，所以起点需要进行一个判断；其次是确定搜索方式，一块板子有两种放法，而且如何选择放置的位置也值得推敲。
有点麻烦，但这道题的解法又很简约，把棋盘视作黑白相间的国际象棋棋盘，再判断所挖去的两个格子的颜色是否相同；根据这种方法，一块1 * 2的板子一定会覆盖一黑一白，若颜色相同，意味着黑白数目不等，则无法完全覆盖，若不同，则可完全覆盖。
我还是太菜了，只能感觉好像是这么回事，但我证明不了，难搞啊。

解决代码：

#include<iostream> 
using namespace std; 
int main(){ int k,a,b,c,d; scanf("%d",&k); for(int i=1;i<=k;++i){ scanf("%d%d%d%d",&a,&b,&c,&d); printf("Scenario #%d:\n%d\n\n",i,(abs(a-c)+abs(b-d))%2==1?1:0); }return 0; 
}

F - Help Jimmy

问题分析：

重点在于问题的分解，先将起点视作左右端点在同一位置的板子，那么对于处在一块板子上的Jimmy，此时需要做出一个选择，究竟是该向左还是向右，对于Jimmy来说，它肯定会选择最优解，而此时我们的最优解就是左右端点中到地面最快的端点，那么，我们就成功把问题分解成了两个子问题，就是求左右端点到地面的最短时间，借助递归来实现问题的分解就行了。
题目的另一个问题应该就是对递归出口以及各种情况的判断。处于一个端点，首先要判断其下方有没有板子，接着再判断是否会摔死，只有能成功抵达下一个板子，我们才能会继续递归下去。
过程中注意先将板子按高度进行一个排序，从高到低，那么才方便进行检索判断。

解决代码：

#include<bits/stdc++.h>
using namespace std;
#define MAX_N 1000 
#define INFINITE 1000000 
//不适合直接使用INT_MAX，有加法，过程中会爆掉，自动取模，导致产生误差，我们需要的是一个尽量大的值就行了 
int t, n, x, y,MAX; 
struct Platform{ int Lx, Rx, h; 
}; 
Platform aPlatform[MAX_N + 10]; 
int aLeftMinTime[MAX_N + 10]; //对于第i块板子，左端到地面的最短时间 
int aRightMinTime[MAX_N + 10];//第i块板子右端到地面的最短时间 
int cnt( Platform p1,Platform p2){//用来排序 ，以高度从高到低进行排序 return p2.h<p1.h; } 
int MinTime( int L, bool bLeft ){//L为板子的编号，bLeft确定是由左端跳下还是右端 int y=aPlatform[L].h; int x; if( bLeft ) x=aPlatform[L].Lx; else x=aPlatform[L].Rx; int i;for(i=L+1;i<=n;i++){//在高度低于该板的板子中找一个可以跳到的板子 if(aPlatform[i].Lx<=x&&aPlatform[i].Rx>=x) break; } if(i<=n){//找到if(y-aPlatform[i].h>MAX)//太高了，跳不下去 return INFINITE; //返回一个最大值 } else{//下方没有板子 if(y>MAX)return INFINITE; elsereturn y; //速度恰为1，高度数值即时间数值 
}
//更多的情况是找到了一个板子，且不会摔死 int nLeftTime=y-aPlatform[i].h+x-aPlatform[i].Lx;//下落时间跟移动时间 int nRightTime=y-aPlatform[i].h+aPlatform[i].Rx-x;//同上 if(aLeftMinTime[i]==0)aLeftMinTime[i]=MinTime(i,true); if(aRightMinTime[i]==0) aRightMinTime[i]=MinTime(i,false); nLeftTime+=aLeftMinTime[i]; nRightTime+=aRightMinTime[i];return min(nLeftTime,nRightTime);
}
int main(){cin>>t;for(int i=0;i<t;i++){memset(aLeftMinTime,0,sizeof(aLeftMinTime)); memset(aRightMinTime, 0, sizeof(aRightMinTime)); cin>>n>>x>>y>>MAX; aPlatform[0].Lx=x; aPlatform[0].Rx=x; aPlatform[0].h=y; for(int j=1;j<=n;j++)cin>>aPlatform[j].Lx>>aPlatform[j].Rx>>aPlatform[j].h; sort(aPlatform,aPlatform+n+1,cnt); cout<<MinTime(0,true)<<endl; }
}