\(Description:\)
废除一段文字, 有若干单词组成, 要使这个文字的难看程度最低, 难看程度为
一个空中空格个数减一的平方.
- \(Sample\) \(Input:\)
- 28
- This is the example you are
actually considering.
\(Sample\) \(Output:\)
Minimal badness is 12.
\(Solution:\)
不会读入, 感觉好像不可做, 正解是貌似居然是动态规划...
考虑设 \(f[i]\) 表示在 \(i\) 之前最小的难看值.
转移:
\(f[i]=min_{j=0}^{i} f[j]+cost(j+1,i)\)
\(cost(j+1,i)\) 就是 \(j+1\) 到 \(i\) 分成一行的难看程度.
算一下 cost 就很裸了...
- #include<bits/stdc++.h>
- using namespace std;
- int n,m;
- const int N=1e4+5,INF=0x3f3f3f3f;
- char s[N];
- int a[N],sum[N],f[N];
- inline int sqr(int x){
- return x*x;
- }
- inline int cost(int l,int r){
- if(l==r){
- if(a[l]<m) return 500;
- else return 0;
- }
- int x=m-(sum[r]-sum[l-1]);
- if(x<0) return INF;
- int y=r-l;
- if(x<y) return INF;
- return (y-x%y)*sqr(x/y-1)+(x%y)*sqr(x/y);
- }
- int main(){
- memset(f,0x3f,sizeof(f));
- f[0]=0;
- scanf("%d",&m);
- while(~scanf("%s",s)) a[++n]=strlen(s);
- for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
- for(int i=1;i<=n;++i) for(int j=0;j<i;++j)
- f[i]=min(f[i],f[j]+cost(j+1,i));
- printf("Minimal badness is %d.\n",f[n]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3027579.html