BZOJ2298: [HAOI2011]problem a

Portal

每个人所在的可行区间为 [l+1,n−r] 。题目就可以转化为求若干个不相交区间的最大权值和。用 n 减最大和就是最少的说谎人数。 f[i]=max(f[l−1] sum[l,r])

【代码】

#include <iostream> #include <cstdio> #include <algorithm> #include <map> #include <vector> #define N 100005 #define INF 1e9 using namespace std; typedef long long ll; typedef pair<int,int> pa; int read() { int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int n; int f[N]; map<pa,int> mp; vector<int>v[N]; int main() { n=read(); for(int i=1;i<=n;i++) { static int x,y,l,r; x=read(),y=read(); l=x+1,r=n-y; if(l>r) continue; mp[make_pair(l,r)]++; if(mp[make_pair(l,r)]==1) v[r].push_back(l); } for(int i=1;i<=n;i++) { f[i]=f[i-1]; for(int j=0;j<v[i].size();j++) f[i]=max(f[i],f[v[i][j]-1]+min(i-v[i][j]+1,mp[make_pair(v[i][j],i)])); } printf("%d\n",n-f[n]); return 0; }