【题意】
在Byteland一共有n家商店，编号依次为1到n。每家商店只会卖一种物品，其中第ii家商店的物品单价为vi ，且它到Byteasar的家的距离为di 。
Byteasar每天都会进行一次购物，第ii天他会选择一个区间[li,ri]，并给自己设定一个距离上限ci ，然后他会在编号在该区间内每家到自己家的距离不超过ci的商店购买最多一件物品，当然他也可以选择什么都不买。回家之后，Byteasar会把今天购物所花的钱的总数sumi记录在账本上。
Byteasar的数学不好，他可能会把花的钱记错。
请写一个程序，帮助Byteasar判断每条记录是否一定是错的。
【分析】
前面是偏序问题，后面问能否拼出某个价格，且价格《=100，可以用动态规划解决。
官方题解：
表示没有想出dis的解决方法，那个dp里面记录最小距离真是太机智。。【是我太蠢。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 20010
#define Maxm 100010
#define Maxd 110
#define INF 0x7fffffff int v[Maxn],d[Maxn]; struct node
{
int l,r,c,sum;
}t[Maxm]; int a[Maxm],a1[Maxm],a2[Maxm];
int f[Maxn][Maxd];
bool ans[Maxm]; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} void get_f(int l,int r,int mid)
{
for(int i=l;i<=r;i++)
for(int j=;j<=;j++)
f[i][j]=INF;
for(int i=l;i<=r;i++) f[i][]=;
int i;
for(i=mid;i>=l;i--)
for(int j=;j>=;j--)
{
f[i][j]=mymin(f[i][j],f[i+][j]);
if(j>=v[i]) f[i][j]=mymin(f[i][j],mymax(f[i+][j-v[i]],d[i]));
}
f[mid+][v[mid+]]=d[mid+];
for(int i=mid+;i<=r;i++)
for(int j=;j>=;j--)
{
f[i][j]=mymin(f[i][j],f[i-][j]);
if(j>=v[i]) f[i][j]=mymin(f[i][j],mymax(f[i-][j-v[i]],d[i]));
}
// for(int i=mid-1;i>=l;i--)
// for(int j=0;j<=100;j++) f[i][j]=mymin(f[i][j],f[i+1][j]);
// for(int i=mid+2;i<=r;i++)
// for(int j=0;j<=100;j++) f[i][j]=mymin(f[i][j],f[i-1][j]);
} void ffind(int l,int r,int x,int y)
{
if(x>y) return;
if(l==r)
{
for(int i=x;i<=y;i++)
if(v[l]==t[a[i]].sum&&d[l]<=t[a[i]].c) ans[a[i]]=;
else ans[a[i]]=;
return;
}
int mid=(l+r)>>;
get_f(l,r,mid);
a1[]=a2[]=;
for(int i=x;i<=y;i++)
{
if(t[a[i]].l<=mid&&t[a[i]].r>mid)
{
ans[a[i]]=;
for(int j=;j<=t[a[i]].sum;j++)
{
if(mymax(f[t[a[i]].l][j],f[t[a[i]].r][t[a[i]].sum-j])<=t[a[i]].c) {ans[a[i]]=;break;}
}
}
else if(t[a[i]].r<=mid)
{
a1[++a1[]]=a[i];
}
else a2[++a2[]]=a[i];
}
int nw=a1[],ww=a2[];
for(int i=;i<=a1[];i++) a[x+i-]=a1[i];
for(int i=;i<=a2[];i++) a[y-i+]=a2[i];
ffind(l,mid,x,x+nw-);
ffind(mid+,r,y-ww+,y);
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&v[i]);
for(int i=;i<=n;i++) scanf("%d",&d[i]);
for(int i=;i<=m;i++) scanf("%d%d%d%d",&t[i].l,&t[i].r,&t[i].c,&t[i].sum);
for(int i=;i<=m;i++) a[i]=i;
ffind(,n,,m);
for(int i=;i<=m;i++)
{
if(ans[i]) printf("");
else printf("");
}
printf("\n");
}
return ;
}
INF开小了，好惨。。
2017-01-16 09:15:55