傳送門(mén)

?

考慮轉(zhuǎn)化為求最多說(shuō)真話的人數(shù)

設(shè)$f(i)$表示排名前$i$的人中最多說(shuō)真話的人的數(shù)量，考慮轉(zhuǎn)移，如果由$j$轉(zhuǎn)移而來(lái)，可以設(shè)$[j,i]$之間的人全都分?jǐn)?shù)相等，那么式子就是$f[i]=f[j-1]+sum([j,i])$，其中$sum([j,i])$表示處在這個(gè)區(qū)間的人數(shù)，全部分?jǐn)?shù)相等，另外如果人數(shù)多于區(qū)間數(shù)，多出來(lái)的人都在說(shuō)謊

1 //minamoto 2 #include<bits/stdc++.h> 3 #define mp(i,j) make_pair(i,j) 4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} 8 inline int read(){ 9 #define num ch-'0' 10 char ch;bool flag=0;int res; 11 while(!isdigit(ch=getc())) 12 (ch=='-')&&(flag=true); 13 for(res=num;isdigit(ch=getc());res=res*10+num); 14 (flag)&&(res=-res); 15 #undef num 16 return res; 17 } 18 const int N=100005; 19 vector<int> a[N];int n,f[N];map<pair<int,int>,int> x; 20 vector<int>::iterator ii; 21 int main(){ 22 // freopen("testdata.in","r",stdin); 23 n=read(); 24 for(int i=1;i<=n;++i){ 25 int l=read(),r=read(); 26 ++l,r=n-r; 27 if(l>r) continue; 28 if(++x[mp(l,r)]==1) a[r].push_back(l); 29 } 30 for(int i=1;i<=n;++i){ 31 f[i]=f[i-1]; 32 for(ii=a[i].begin();ii!=a[i].end();++ii) 33 cmax(f[i],f[(*ii)-1]+min(i-(*ii)+1,x[mp(*ii,i)])); 34 } 35 printf("%d\n",n-f[n]); 36 return 0; 37 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/bztMinamoto/p/9751798.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2519 [HAOI2011]problem a的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。