NOI2009诗人小G
Description
Input
Output
对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出”Too hard to arrange”(不包含引号)。每个输出后面加”——————–“
Sample Input
4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet
Sample Output
108
——————–
32
——————–
Too hard to arrange
——————–
1000000000000000000
——————–「样例说明」
前两组输入数据中每行的实际长度均为6，后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。
——————–
32
——————–
Too hard to arrange
——————–
1000000000000000000
——————–「样例说明」
前两组输入数据中每行的实际长度均为6，后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。
HINT
总共10个测试点，数据范围满足：
测试点 T N L P
1 ≤10 ≤18 ≤100 ≤5
2 ≤10 ≤2000 ≤60000 ≤10
3 ≤10 ≤2000 ≤60000 ≤10
4 ≤5 ≤100000 ≤200 ≤10
5 ≤5 ≤100000 ≤200 ≤10
6 ≤5 ≤100000 ≤3000000 2
7 ≤5 ≤100000 ≤3000000 2
8 ≤5 ≤100000 ≤3000000 ≤10
9 ≤5 ≤100000 ≤3000000 ≤10
10 ≤5 ≤100000 ≤3000000 ≤10
所有测试点中均满足句子长度不超过30。
题解
https://www.byvoid.com/blog/noi-2009-poet
byvoid写的题解真是神到不能直视啊。。我都不敢写了。。
写出dp方程30分。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> #define ll long long #define inf 9000000000000000000 #define MAX 1000000000000000000LL using namespace std; int T,n,l,p,top; int q[2005]; ll sum[2005],f[2005],from[2005]; char ch[2005][35]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll pow(ll x) { if(x<0)x=-x; ll ans=1; for(int i=1;i<=p;i++) if((long double)ans*x>MAX)return MAX+1; else ans*=x; return ans; } void dp() { for(int i=1;i<=n;i++)f[i]=inf; f[0]=0; for(int i=1;i<=n;i++) for(int j=0;j<i;j++) { ll t=f[j]+pow(sum[i]-sum[j]+(i-j-1)-l); if(t<=f[i])f[i]=t,from[i]=j; } } int main() { T=read(); while(T--) { n=read();l=read();p=read(); for(int i=1;i<=n;i++) scanf("%s",ch[i]); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+strlen(ch[i]); dp(); if(f[n]>MAX) puts("Too hard to arrange"); else printf("%lld\n",f[n]); puts("--------------------"); } return 0; } |
加个贪心。。50分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> #define ll long long #define inf 9000000000000000000 #define MAX 1000000000000000000LL using namespace std; int T,n,l,p,top; int q[100005]; ll sum[100005],f[100005],from[100005]; char ch[100005][35]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll pow(ll x) { if(x<0)x=-x; ll ans=1; for(int i=1;i<=p;i++) if((long double)ans*x>MAX)return MAX+1; else ans*=x; return ans; } void dp() { for(int i=1;i<=n;i++)f[i]=inf; f[0]=0; for(int i=1;i<=n;i++) for(int j=i-1;j>=0;j--) { if(sum[i]-sum[j]>=2*l)break; ll t=f[j]+pow(sum[i]-sum[j]+(i-j-1)-l); if(t<=f[i])f[i]=t,from[i]=j; } } int main() { T=read(); while(T--) { n=read();l=read();p=read(); for(int i=1;i<=n;i++) scanf("%s",ch[i]); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+strlen(ch[i]); dp(); if(f[n]>MAX) puts("Too hard to arrange"); else printf("%lld\n",f[n]); puts("--------------------"); } return 0; } |
50-70分好像是玩具装箱吧。。。
满分做法。。。
由打表发现决策单调性。。。证明orz
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> #define ll long double #define inf 9000000000000000000 #define MAX 1000000000000000000LL using namespace std; int T,n,l,p,top; ll sum[100005],f[100005],from[100005]; char ch[100005][35]; struct data{int l,r,p;}q[100005]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll pow(ll x) { if(x<0)x=-x; ll ans=1; for(int i=1;i<=p;i++) ans*=x; return ans; } ll cal(int j,int i) { return f[j]+pow(sum[i]-sum[j]+(i-j-1)-l); } int find(data t,int x) { int l=t.l,r=t.r; while(l<=r) { int mid=(l+r)>>1; if(cal(t.p,mid)<cal(x,mid)) l=mid+1; else r=mid-1; } return l; } void dp() { int head=1,tail=0; q[++tail]=(data){0,n,0}; for(int i=1;i<=n;i++) { if(head<=tail&&i>q[head].r)head++; f[i]=cal(q[head].p,i); from[i]=q[head].p; if(head>tail||cal(i,n)<=cal(q[tail].p,n)) { while(head<=tail&&cal(i,q[tail].l)<=cal(q[tail].p,q[tail].l)) tail--; if(head>tail) q[++tail]=(data){i,n,i}; else { int t=find(q[tail],i); q[tail].r=t-1; q[++tail]=(data){t,n,i}; } } } } int main() { T=read(); while(T--) { n=read();l=read();p=read(); for(int i=1;i<=n;i++) scanf("%s",ch[i]); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+strlen(ch[i]); dp(); if(f[n]>MAX) puts("Too hard to arrange"); else printf("%lld\n",(long long)f[n]); puts("--------------------"); } return 0; } |
Subscribe
计数器 9322298
OI 课件=>
OI 课件=>