今天做的非常差，只有130分（人家都有AK的！！） 好吧20+100+10=130分。 T1:天平 http://172.16.0.132/senior/#contest/show/2068/0 比赛时候，我用dp做，很傻逼。结果答案错误…… 其实，可以直接爆搜加一点剪枝。或者类似中途相遇法之类的……
#include<cstdio> #include<iostream> #define max(x,y) (((x)>(y))? x:y) using namespace std; int n,c; long long f[41],v[41],x,ans; void dg(int t,int s) { if (s>c) return; if (s+f[t-1]<=c) { ans=max(s+f[t-1],ans); return; } ans=max(ans,s); int i; for (i=1;i<t;++i) dg(i,s+v[i]); } int main() { scanf("%d%d",&n,&c); int i,j,k; long long nn; for (i=1;i<=n;++i) { scanf("%lld",&x); if (x<=c) { v[i]=x; nn=i; f[i]=f[i-1]+x; } } dg(nn+1,0); printf("%lld\n",ans); }T2:游历的路线(lines) http://172.16.0.132/senior/#contest/show/2068/1 比赛时唯一A了的题，这是一道dp题，设f[i][j]表示第i天到达j地的最优值。 还有记录g[i][j][k]表示第i天，从第j个地方到第k个地方的费用。 直接o(1)调用就好了。
#include<cstdio> #include<iostream> #include<cstring> #define min(x,y) (((x)<(y))? x:y) using namespace std; int g[201][101][101],f[201][101],n,m; int main() { freopen("lines.in","r",stdin); freopen("lines.out","w",stdout); scanf("%d%d",&n,&m); int x,y,i,j,t,a[21],k,l; x=1; y=2; for (i=1;i<=n*(n-1);++i) { if (x==y) y++; if (y>n) { x++; y=1; } scanf("%d",&t); for (j=1;j<=t;++j) scanf("%d",&a[j]); for (j=1;j<=m;++j) g[j][x][y]=a[(j-1)%t+1]; ++y; } memset(f,127,sizeof(f)); for (i=1;i<=n;++i) f[1][i]=g[1][1][i]; for (i=2;i<=m;++i) { for (j=1;j<=n;++j) for (k=1;k<=n;++k) if (j!=k&&g[i][k][j]>0&&f[i-1][k]>0) f[i][j]=min(f[i][j],f[i-1][k]+g[i][k][j]); } if (f[m][n]==2139062143) printf("0\n"); else printf("%d\n",f[m][n]); }T3:【NOI2015模拟8.17】最短路（shortest） http://172.16.0.132/senior/#contest/show/2068/2 详见同作者的题解：http://blog.csdn.net/cdy1206473601/article/details/76777699
