bzoj1584 [ Usaco2009 Mar ] --DP
2018-06-17 23:26:09来源:未知 阅读 ()
题目大意:
有N头奶牛,每头那牛都有一个标号Pi,1 <= Pi <= M <= N <= 40000。现在Farmer John要把这些奶牛分成若干段,定义每段的不河蟹度为:若这段里有k个不同的数,那不河蟹度为k*k。那总的不河蟹度就是所有段的不河蟹度的总和。
思路:
显然如果连续的一段数字相同,我们可以把它们合并成一个数字。
用f[i]表示在1~i这一段的最小不河蟹度。因为答案最大为n,显然不可能出现一段中有超过sqrt(n)个不同的数。
定义b[j],使b[j]+1~i中不同的数的个数等于j且b[j]最小,那么可以得到:f[i]=min{f[j]+j*j},j<=sqrt(n)
怎么求b[j]呢?定义p[k]表示值为k的数前一次出现的位置、c[j]表示b[j]+1~i中有多少个不同的数。
枚举i,更新p,c,对于b[j],若c[j]>j,则需要将b[j]增大,直到a[b[j]]在b[j]+1~i中不出现,一个while即可。
时间复杂度O(n*sqrt(n))
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 char buf[10000000],*p1=buf; 7 inline void Read(int& x){ 8 char c=*p1++; 9 for(;c<'0'||c>'9';c=*p1++); 10 for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=*p1++); 11 } 12 int i,j,k,n,m,x,a[40001],c[40001],f[40001],Last,Pre,p[40001],b[201],Num; 13 bool B[201]; 14 int main() 15 { 16 fread(buf,1,10000000,stdin); 17 Read(n);Read(m); 18 for(i=1;i<=n;i++){ 19 Read(x); 20 if(x!=a[Num])a[++Num]=x; 21 } 22 n=Num;m=sqrt((double)n); 23 memset(f,127,sizeof(f)); 24 for(i=1,f[0]=0;i<=n;i++){ 25 for(j=1;j<=m;j++)if(p[a[i]]<=b[j])c[j]++; 26 for(j=1,p[a[i]]=i;j<=m;j++) 27 if(c[j]>j){ 28 k=b[j]+1; 29 while(p[a[k]]!=k)k++; 30 b[j]=k;c[j]--; 31 } 32 for(j=1;j<=m;j++) 33 if(f[b[j]]+j*j<f[i])f[i]=f[b[j]]+j*j; 34 } 35 printf("%d",f[n]); 36 return 0; 37 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷 P2947 [USACO09MAR]向右看齐Look Up 2019-08-16
- 『ACM C++』Virtual Judge | 两道基础题 - The Architect Om 2019-02-25
- BZOJ1576: [Usaco2009 Jan]安全路经Travel(最短路 并查集) 2018-09-10
- BZOJ3398: [Usaco2009 Feb]Bullcow 牡牛和牝牛(dp) 2018-09-05
- C# Xamarin移动开发基础进修篇 2018-06-27
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash