网站主流系统,网赌网站怎么建设,创建公司网站,项目计划书大纲$f[i][j]$表示消灭起始时间在$(i,j)$内的外星人所花费的最小代价。 考虑在这个区间内距离最远的外星人h#xff0c;在他的区间中一定要选一个点要开一炮#xff0c;而且这一炮可以顺便把其他跨过这个点的敌人消灭#xff0c;剩下只需消灭没有跨过这个点的敌人。 枚举开炮时间…$f[i][j]$表示消灭起始时间在$(i,j)$内的外星人所花费的最小代价。 考虑在这个区间内距离最远的外星人h在他的区间中一定要选一个点要开一炮而且这一炮可以顺便把其他跨过这个点的敌人消灭剩下只需消灭没有跨过这个点的敌人。 枚举开炮时间$f[i][j]min(f[i][k]f[k][j]d[h])$. 区间需要离散化。 #includeiostream
#includecstdio
#includecstring
#includealgorithm
#define N 605
using namespace std;
int n;
int li[N],cnt;
int a[N],b[N],d[N];
int f[N][N];
int main()
{int cas;scanf(%d,cas);while(cas--){scanf(%d,n);cnt0;for(int i1;in;i){scanf(%d%d%d,a[i],b[i],d[i]);li[cnt]a[i];li[cnt]b[i];}sort(li1,licnt1);cntunique(li1,licnt1)-li-1;for(int i1;in;i){a[i]lower_bound(li1,licnt1,a[i])-li;b[i]lower_bound(li1,licnt1,b[i])-li;}cnt;for(int l0;lcnt;l){for(int i0;icnt-l;i){int jil;int h-1;for(int k1;kn;k){if(a[k]ib[k]j){if(h-1||d[k]d[h])hk;}}if(h-1)f[i][j]0;else{f[i][j]0x3f3f3f3f;for(int ka[h];kb[h];k){f[i][j]min(f[i][j],f[i][k]f[k][j]d[h]);}}}}printf(%d\n,f[0][cnt]);}return 0;
}转载于:https://www.cnblogs.com/ezyzy/p/6659204.html
