题目
LA4258 Metal
题解
是不是因为这道题太简单了所以大家都没交而且一篇题解也没有qwq。
不过没有题解到是强迫我思考，估计有题解的话我是想不出来这题的。首先这个问题可以等价成，从x最小的点找两条路径到x最大的点，并且要满足单调这个性质。其实你可以发现，单调就是为了保证路径总是从x小的点走向x大的点（比较显然，不懂可以自己举个栗子），然后就跟以前做过的题很相似了。
分上下两路讨论（上路u，下路d）用 dp[i][j]表示u到i，d到j的方案数，但是到这里还不够，转移的时候要判断是否相交。一开始脑残了，因为只记了最后一个点，所以只判断了连线与最后一个点的位置关系，如果出现这样的情况，要判断A是否能走到B，我就GG了，然后就卡住了qwq。
然后脑子一抽，如果d从A走到B那不是说明中间的点全是u走的吗？所以我只需要预处理一遍，对于u和d分别处理两个G数组G[i][j]表示能否从i到j，这个应该是很好处理的。然后的话，这道题采用“用现有状态去更新之后的状态“的方法要比“推算出之后状态需要哪些之前的状态然后更新”好写一些。然后注意边界就是dp[1][2]=dp[2][1]=1。统计答案的时候是现有状态有一个点走到了n-1，然后根据能否转移，统计答案。
代码
//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=50+10;int n,dp[maxn][maxn];struct Node{int x,y;Node(int x=0,int y=0):x(x),y(y){}inline void input(){
scanf("%d%d",&x,&y);}bool operator < (const Node &rhs)const{
return x<rhs.x;}
}a[maxn];struct Line{double k,b;Line(Node A,Node B){k=1.0*(A.y-B.y)/(A.x-B.x);b=A.y-k*A.x;}double f(double x){
return k*x+b;}
};int G1[maxn][maxn],G2[maxn][maxn];
//G1是上面的 G2是下面的 inline void init_G()
{for(int i=1;i<=n;++i)for(int j=i+1;j<=n;++j){Line t(a[i],a[j]);int ok1=1,ok2=1;for(int k=i+1;k<j;++k) if(t.f(a[k].x) <= a[k].y) {ok1=0;break;}for(int k=i+1;k<j;++k) if(t.f(a[k].x) >= a[k].y) {ok2=0;break;}G1[i][j]=ok1;G2[i][j]=ok2;}
}inline void solve()
{memset(dp,0,sizeof dp);cin>>n;for(int i=1;i<=n;++i) a[i].input();sort(a+1,a+n+1);init_G();dp[2][1]=dp[1][2]=1;long long ans=0;for(int i=1;i<n;++i)for(int j=1;j<n;++j) if(dp[i][j]){//G为1表示可走，统计贡献，否则不统计 int k=max(i,j)+1;if(i==n-1){ans+=dp[i][j]*(G2[j][n]&&G1[i][n]);continue;}if(j==n-1){ans+=dp[i][j]*(G1[i][n]&&G2[j][n]);continue;}if(G1[i][k]) dp[k][j]+=dp[i][j];if(G2[j][k]) dp[i][k]+=dp[i][j];}printf("%lld\n",ans);
}int main()
{int T;cin>>T;while(T--) solve();return 0;
}