有个平面。人可以从任意位置出发，每秒不动或上下左右走一个。
有(n)个传送塔。每时每刻都可以瞬间传送到之前遍历过的传送塔。
有(m)个目标点，每个目标点规定了个到达时间，表示在那个时间刚好在那里可以得一分。
问最高能得多少分。
(nle 14,mle 100)
设(F_{S,i})表示走了(S)中的传送塔，得了(i)分的最少时间。(G_{S,i})表示走了(S)中的传送塔，到目标点(i)的最大得分。两者互相转移。
转移：
- 从某个目标点直接到达下一个目标点。
- 从某个目标点直接到达下一个没有被遍历过的塔。
- 从某个目标点瞬移到任意被遍历过的塔。
- 从塔走到下一个没有被遍历过的塔。
- 从塔走到下一个目标点。
列出方程，转移即可。转移顺序得当可以(O(2^nm(n+m)))。
using namespace std;
#include <bits/stdc++.h>
#define N 14
#define M 120
#define ll long long
#define INF 2000000000
int n,m;
int X[N],Y[N];
struct DOT{
int x,y,t;
} d[M];
bool cmpd(DOT a,DOT b){return a.t<b.t;}
ll diss[1<<N][M],dis[M][M];
ll f[1<<N][M],g[1<<N][M];
void gmin(ll &a,ll b){a=min(a,b);}
void gmax(ll &a,ll b){a=max(a,b);}
int main(){
scanf("%d%d",&n,&m);
for (int i=0;i<n;++i)
scanf("%d%d",&X[i],&Y[i]),d[i+m]={X[i],Y[i]};
for (int i=0;i<m;++i)
scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].t);
sort(d,d+m,cmpd);
for (int i=0;i<m;++i)
for (int j=0;j<m+n;++j)
dis[i][j]=abs(d[i].x-d[j].x)+abs(d[i].y-d[j].y);
for (int s=0;s<1<<n;++s)
for (int i=0;i<m+n;++i){
diss[s][i]=INF;
for (int j=0;j<n;++j)
if (s>>j&1)
gmin(diss[s][i],abs(X[j]-d[i].x)+abs(Y[j]-d[i].y));
}
memset(f,63,sizeof f);
memset(g,192,sizeof g);
for (int i=0;i<n;++i) f[1<<i][0]=0;
for (int i=0;i<m;++i) g[0][i]=1;
for (int s=0;s<1<<n;++s){
for (int i=0;i<m;++i){
//f->g
for (int j=i;j>=0;--j)
if (f[s][j]+diss[s][i]<=d[i].t){
gmax(g[s][i],j+1);
break;
}
//g->g
for (int j=0;j<i;++j)
if (d[j].t+dis[j][i]<=d[i].t)
gmax(g[s][i],g[s][j]+1);
//g->f
if (g[s][i]<0) continue;
gmin(f[s][g[s][i]],d[i].t);
for (int j=0;j<n;++j)
if (s>>j&1^1)
gmin(f[s|1<<j][g[s][i]],d[i].t+dis[i][j+m]);
}
//f->f
for (int i=0;i<=m;++i)
for (int j=0;j<n;++j)
if (s>>j&1^1)
gmin(f[s|1<<j][i],f[s][i]+diss[s][j+m]);
}
for (int i=m;i>=0;--i)
for (int s=0;s<1<<n;++s)
if (f[s][i]<INF){
printf("%d
",i);
return 0;
}
return 0;
}