效率别吐槽

poj1014
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=11,M=60010,V=6001;
int i,j,k,o,s[N],sum,w[V],p,ss,q[V],g,b,tmp,n;
bool f[M],ff;
int main()
{
while (1)
{
o++;sum=p=0;
for (i=1;i<=6;i++)
{
scanf("%d",&s[i]);sum+=s[i]*i;
if (s[i]) {p++;w[p]=i;q[p]=s[i];}
}
if (sum==0) break;
printf("Collection #%d:\n",o);
if (sum%2==1) {printf("Can't be divided.\n\n");continue;}
memset(f,0,sizeof(f));sum/=2;n=p;
for (i=1;i<=n;i++)
{
g=b=1;
tmp=w[i]*2;
while (1)
{
g*=2;
if (b+g<q[i]) {p++;w[p]=tmp;}
else if (b+g==q[i]) {p++;w[p]=tmp;break;}
else {p++;b=q[i]-b;w[p]=w[i]*b;break;}
b+=g;tmp*=2;
}
}
f[0]=1;
for (i=1;i<=p;i++)
{
for (j=sum;j>=w[i];j--)
if (f[j-w[i]]) f[j]=1;
if (f[sum]) break;
}
if (f[sum]) printf("Can be divided.\n\n");
else printf("Can't be divided.\n\n");
}
return 0;
}

poj1252
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=8,M=2000,V=1000000000;
int i,j,k,n,o,f[M+11],m,a[N];
double pin;
int main()
{
scanf("%d",&o);
while (o)
{
for (i=1;i<=6;i++) scanf("%d",&a[i]);
for (i=1;i<=M;i++) f[i]=V;
for (i=1;i<=6;i++)
for (j=0;j+a[i]<=M;j++) f[j+a[i]]=min(f[j]+1,f[j+a[i]]);
for (i=1;i<=6;i++)
for (j=M;j-a[i]>=0;j--) f[j-a[i]]=min(f[j]+1,f[j-a[i]]);
pin=m=0;
for (i=1;i<=100;i++)
{
if (f[i]>m) m=f[i];
pin+=f[i];
}
pin/=100.0;
printf("%0.2lf %d\n",pin,m);
o--;
}
return 0;
}

poj1742
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=111111;
int i,j,k,n,m,a[N],b[N],p,x,y,t,ans,u[N];
bool f[N];
int main()
{
while (1)
{
scanf("%d%d",&n,&m);
if (n==0) break;ans=0;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++) scanf("%d",&b[i]);
for (i=1;i<=m;i++) f[i]=0;f[0]=1;
for (i=1;i<=n;i++)
{
memset(u,0,sizeof(u));
for (j=a[i];j<=m;j++) if ((!f[j])&&(f[j-a[i]])&&(u[j-a[i]]<b[i]))
{
f[j]=1;u[j]=u[j-a[i]]+1;ans++;
}
}
printf("%d\n",ans);
}
return 0;
}

poj1837
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=25,N=20010,V=7500,L=15000;
int i,j,k,n,c,s[M],w[M],x,y,f[M][N];
int main()
{
while (cin>>c>>n)
{
for (i=1;i<=c;i++) scanf("%d",&s[i]);
memset(f,0,sizeof(f));f[0][V]=1;
for (i=1;i<=n;i++) scanf("%d",&w[i]);
for (i=1;i<=n;i++)
for (j=0;j<=L;j++)
for (k=1;k<=c;k++)
if (j-s[k]*w[i]>=0) f[i][j]+=f[i-1][j-s[k]*w[i]];
printf("%d\n",f[n][V]);
}
return 0;
}

poj2576
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=111,V=100000000,N=23010;
int i,j,k,n,w[M],m,sum,s,o,a,b;
bool f[M][N];
int main()
{
while (scanf("%d",&n)==1)
{
sum=0;memset(f,0,sizeof(f));f[0][0]=1;
for (i=1;i<=n;i++) {scanf("%d",&w[i]);sum+=w[i];}
if (n==1) {printf("0 %d\n",w[1]);continue;}
s=sum/2;m=(n+1)/2;
i=0;
while (1)
{
i++;o=min(i,m);
for (j=o;j>=1;j--)
{
for (k=w[i];k<=s;k++)
if (!f[j][k]&&f[j-1][k-w[i]]) f[j][k]=1;
}
if (i==n) break;
}
for (i=s;i>=0;i--)
if (f[m][i]) break;
a=i;
if (n%2==1)
{
for (i=s;i>=0;i--)
if (f[m-1][i]) break;
b=i;
if (b>a) a=b;
}
printf("%d %d\n",a,sum-a);
}
return 0;
}

poj1948
#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=1811,N=44;
int i,j,k,n,a[N],sum,o,x,y,z,xx,yy,zz,s,ans;
double v;
bool f[M][M];
int main()
{
scanf("%d",&n);ans=-1;
sum=0;memset(f,0,sizeof(f));
for (i=1;i<=n;i++) {scanf("%d",&a[i]);sum+=a[i];}
o=sum/2;f[0][0]=1;
for (i=1;i<=n;i++)
for (j=o-1;j>=0;j--)
for (k=j;k>=0;k--)
if (((j>=a[i])&&(f[j-a[i]][k]))||((k>=a[i])&&(f[j][k-a[i]]))) f[j][k]=1;
for (i=1;i<=o;i++)
for (j=i;j>=1;j--)
if (f[i][j])
{
k=sum-i-j;
if (i+j>k&&i+k>j&&j+k>i)
{
v=(i+j+k)*1.0/2;
s=int(sqrt(v*(v-i)*(v-j)*(v-k)*1.0)*100);
if (s>ans) ans=s;
}
}
cout<<ans<<endl;
return 0;
}

poj1976
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int M=50010;
int i,j,k,n,m,o,sum[M],a[M],f[4][M],v;
int main()
{
cin>>o;
while (o)
{
scanf("%d",&n);sum[0]=0;
for (i=1;i<=n;i++) {scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}
scanf("%d",&m);
for (i=1;i<=3;i++)
for (j=1;j<=n;j++) f[i][j]=-1;
for (i=1;i<=3;i++)
{
v=n-m;
for (j=i-1;j<=v;j++)
for (k=1;k<=m;k++)
{
f[i][j+k]=max(f[i][j+k],f[i][j+k-1]);
if (f[i-1][j]!=-1) f[i][j+k]=max(f[i][j+k],f[i-1][j]+sum[j+k]-sum[j]);
}
}
//for (i=1;i<=n;i++) cout<<f[1][i]<<endl;
printf("%d\n",f[3][n]);
o--;
}
return 0;
}

poj3211
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int M=100010,N=110,V=15;
int i,j,k,n,m,a[V][N],ans,o,sum,v,tmp;
string color[V],name;
bool f[M];
int main()
{
while (1)
{
scanf("%d%d",&n,&m);
if (n+m==0) break;memset(a,0,sizeof(a));
for (i=1;i<=n;i++) cin>>color[i];
for (i=1;i<=m;i++)
{
scanf("%d",&k);cin>>name;
for (j=1;j<=n;j++)
if (color[j]==name) {a[j][0]++;a[j][a[j][0]]=k;break;}
}
ans=0;
for (o=1;o<=n;o++)
if (a[o][0])
{
sum=0;
for (i=1;i<=a[o][0];i++) sum+=a[o][i];
v=sum/2;f[0]=1;
for (i=1;i<=sum;i++) f[i]=0;
for (i=1;i<=a[o][0];i++)
for (j=v;j>=a[o][i];j--) if (!f[j]&&f[j-a[o][i]]) f[j]=1;
for (i=v;i>=0;i--)
if (f[i]) break;
tmp=sum-i;ans+=tmp;
}
printf("%d\n",ans);
}
return 0;
}

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int M=1111;
int i,j,k,n,a[M],f[M],ans;
int main()
{
cin>>n;ans=f[1]=1;
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=2;i<=n;i++)
{
f[i]=1;
for (j=1;j<i;j++)
if (a[i]>a[j])
{
f[i]=max(f[j]+1,f[i]);
if (f[i]>ans) ans=f[i];
}
}
printf("%d\n",ans);
return 0;
}

poj1159 低效率
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int M=5111;
int i,j,k,n,o,f[2][M],s,ans,v,u;
char a[M],b[M];
int main()
{
scanf("%d",&n);gets(a);
for (i=1;i<=n;i++) scanf("%c",&a[i]);
if (n==1) printf("0\n");
else if (n==2&&a[0]==a[1]) printf("0\n");
else if (n==2&&a[0]!=a[1]) printf("1\n");
else
{
s=n;for (i=1;i<=n;i++,s--) b[i]=a[s];
s=n;u=1;
for (i=1;i<=s;i++)
{
v=n-i;k=!u;
for (j=1;j<=v;j++)
{
if (b[j]==a[i]) f[k][j]=f[u][j-1]+1;
else f[k][j]=max(f[k][j-1],f[u][j]);
if (f[k][j]*2>ans) ans=f[k][j]*2;
}
u=!u;
}
for (i=1;i<=s;i++) f[1][i]=f[0][i]=0;
u=1;
for (i=2;i<=s+1;i++)
{
v=n-i;k=!u;
for (j=1;j<=v;j++)
{
if (b[j]==a[i-1]) f[k][j]=f[u][j-1]+1;
else f[k][j]=max(f[k][j-1],f[u][j]);
if (f[k][j]*2+1>ans) ans=f[k][j]*2+1;
}
u=!u;
}
cout<<n-ans<<endl;
}
return 0;
}

poj2127
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int M=555;
int i,j,k,n,m,w[M],f[M],a[M][M],x,y,mx,b[M][M],mj,ans[M];
int main()
{
cin>>m;
for (i=1;i<=m;i++) scanf("%d",&w[i]);
cin>>n;
for (i=1;i<=n;i++) scanf("%d",&f[i]);
for (i=1;i<=m;i++)
{
k=0;
for (j=1;j<=n;j++)
{
a[i][j]=a[i-1][j];b[i][j]=-1;
if (w[i]==f[j]) {a[i][j]=k+1;b[i][j]=mj;}
else if ((w[i]>f[j])&&(k<a[i-1][j])) {k=a[i-1][j];mj=j;}
if (mx<a[i][j]) {mx=a[i][j];x=i;y=j;}
}
}
cout<<mx<<endl;k=mx;
while (mx)
{
if (b[x][y]>-1)
{
ans[mx]=f[y];y=b[x][y];mx--;
}
x--;
}
for (i=1;i<k;i++) printf("%d ",ans[i]);
cout<<ans[k]<<endl;
return 0;
}

poj2250
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int M=555;
int i,j,k,f[M][M],n,m,s;
string a[M],b[M];
bool ff;
void st(int n,int m)
{
if (s==f[::n][::m]) return;
if (a[n]==b[m])
{
s++;
st(n-1,m-1);
if (ff) ff=0;
else printf(" ");
cout<<a[n];
}
else if (f[n][m-1]==f[n][m]) {st(n,m-1);return;}
else if (f[n-1][m]==f[n][m]) {st(n-1,m);return;}
}
int main()
{
while (cin>>a[1])
{
ff=1;n=1;m=0;
while (1)
{
n++;cin>>a[n];
if (a[n]=="#") {n--;break;}
}
while (1)
{
m++;cin>>b[m];
if (b[m]=="#") {m--;break;}
}
for (i=0;i<=n;i++)
for (j=0;j<=m;j++) f[i][j]=0;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=max(f[i-1][j],f[i][j-1]);
s=0;
st(n,m);printf("\n");
}
return 0;
}

poj1390：
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
const int M=222;
int i,j,k,n,cnt,o,a[M],f[M][M][M],b[M],frank,c[M],tmp,v,l,u;
int main()
{
cin>>o;
while (cnt!=o)
{
cnt++;printf("Case %d: ",cnt);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
frank=1;b[1]=1;
for (i=2;i<=n;i++)
{
if (a[i]==a[i-1]) b[frank]++;
else
{
frank++;b[frank]=1;a[frank]=a[i];
}
}
for (i=1;i<=frank;i++) c[i]=0;
for (i=frank-1;i>=1;i--)
for (j=i+1;j<=frank;j++) if (a[i]==a[j]) c[i]+=b[j];
for (i=1;i<=frank;i++)
for (j=1;j<=frank;j++)
for (k=0;k<=frank;k++) f[i][j][k]=0;
for (l=1;l<=frank;l++)
{
u=frank-l+1;
for (i=1;i<=u;i++)
{
j=i+l-1;
for (k=0;k<=c[j];k++)
{
v=k+b[j];
f[i][j][k]=f[i][j-1][0]+v*v;
for (tmp=i;tmp<j;tmp++) if (a[j]==a[tmp]) f[i][j][k]=max(f[i][j][k],f[tmp+1][j-1][0]+f[i][tmp][v]);
}
}
}
printf("%d\n",f[1][frank][0]);
}
return 0;
}