远古数据AC代码

#include<cstdio> #include<cstring> #include<cmath> using namespace std; int k,m; int a[501],f[501][501],d[501],L[501],R[501],v[501][501]; /*int print(int i,int j) { int x,t; if(j==0)return 0; if(j==1) { printf("1 %d\n",i); return 0; } t=i; x=a[i]; while(x+a[t-1]<=f[k][m]) { x+=a[t-1]; t--; } print(t-1,j-1); printf("%d %d\n",t,i); }*/ int main() { scanf("%d%d",&m,&k); //if(m==0&&k==0)return 0; for(int i=0;i<=500;i++) { for(int j=0;j<=500;j++) { f[i][j]=0x7fffffff; } } for(int i=1;i<=m;i++) { scanf("%d",&a[i]); d[i]=d[i-1]+a[i]; f[1][i]=d[i]; } for(int i=2;i<=k;i++) { for(int j=1;j<=m;j++) { for(int h=0;h<=j;h++) { if(fmax(f[i-1][h],d[j]-d[h])<f[i][j]) { f[i][j]=fmax(f[i-1][h],d[j]-d[h]); v[i][j]=h; } } } } int tmp=m; for(int i=k;i>=1;i--) { R[i]=tmp; L[i]=v[i][tmp]+1; tmp=v[i][tmp]; } for(int i=1;i<=k;i++) { printf("%d %d\n",L[i],R[i]); } return 0; }

正常数据AC代码

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int s[505],f[505][505],a[505]; int k,m; void print(int i,int j) { if(j==0)return ; if(j==1) { printf("1 %d\n",i); return ; } int t=i; int x=a[i]; while((x+a[t-1]<=f[k][m])&&(t)) { x+=a[t-1]; t--; } print(t-1,j-1); printf("%d %d\n",t,i); } int main() { scanf("%d%d",&m,&k); for(int i=0;i<=501;i++) { for(int j=0;j<=501;j++) { f[i][j]=2147483640; } } for(int i=1;i<=m;i++) { scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; f[1][i]=s[i]; } for(int i=2;i<=k;i++) { for(int j=1;j<=m;j++) { for(int k=0;k<=j;k++) { f[i][j]=min(f[i][j],max(f[i-1][k],s[j]-s[k])); } } } print(m,k); return 0; }

差异：

远古数据要让前面的人少抄写，并且可以不吵，正常数据每人都抄。