1
                        /*
                        背包问题的变式
                        */
                         2 #include<iostream>
 3usingnamespace std;
 4 #include<cstdio>
 5 #include<cstring>
 6#define N 105
 7#define S 10010
 8int n,s,a[N];
 9int minv[S],maxv[S];
10int main()
11{
12     scanf("%d%d",&n,&s);
13for(int i=1;i<=n;++i)
14       scanf("%d",&a[i]);
15     memset(minv,99,sizeof(minv));
16     memset(maxv,-99,sizeof(maxv));
17     minv[0]=maxv[0]=0;
18for(int i=1;i<=s;++i)
19for(int j=1;j<=n;++j)
20if(i>=a[j])
21      {
22           minv[i]=min(minv[i],minv[i-a[j]]+1);
23             maxv[i]=max(maxv[i],maxv[i-a[j]]+1);
24      }
25     printf("%d\n%d",minv[s],maxv[s]);
26return0;
27 }

                         1
                        #define N 100
 2 #include<cstring>
 3 #include<iostream>
 4usingnamespace std;
 5 #include<cstdio>
 6bool G[N][N];
 7int d[N],n,t=0;
 8struct Lf{
 9int x,y,z;
10}lf[N];
11void input()
12{
13     memset(G,false,sizeof(G));
14     memset(d,0,sizeof(d));
15int x,y,z;
16     t=0;
17for(int i=1;i<=n;++i)
18    {
19         scanf("%d%d%d",&x,&y,&z);
20         ++t;
21         lf[t].x=x;lf[t].y=y;lf[t].z=z;
22         ++t;
23         lf[t].x=x;lf[t].y=z;lf[t].z=y;
24         ++t;
25         lf[t].x=y;lf[t].y=z;lf[t].z=x;
26    }
2728}
29void build_tu()
30{
31for(int i=1;i<=t;++i)
32for(int j=1;j<i;++j)
33      {
34if(lf[i].x<lf[j].x&&lf[i].y<lf[j].y)
35             G[i][j]=true;
36if(lf[i].x<lf[j].y&&lf[i].y<lf[j].x)
37             G[i][j]=true;
38if(lf[j].x<lf[i].x&&lf[j].y<lf[i].y)
39             G[j][i]=true;
40if(lf[j].x<lf[i].y&&lf[j].y<lf[i].x)
41             G[j][i]=true;
42      }
43}
44int dp(int k)
45{
46if(d[k]>0) return d[k];
47     d[k]=lf[k].z;
48for(int i=1;i<=t;++i)
49if(G[k][i])  d[k]=max(d[k],dp(i)+lf[k].z);
50return d[k];
51}
52int main()
53{
54int kase=0;
55while(scanf("%d",&n)==1&&n)
56    {
57         ++kase;
58        input();
59        build_tu();
60int ans=0;
61for(int i=1;i<=t;++i)
62        {
63             ans=max(ans,dp(i));
64        }
65         printf("Case %d: maximum height = %d\n",kase,ans);
66    }
67return0;
68 }

                        
                            
 1 #include<cstring>
 2#define N 1008
 3 #include<cmath>
 4 #include<iostream>
 5usingnamespace std;
 6 #include<cstdio>
 7int n;
 8struct Zb{
 9double x,y;
10}zb[N];
11double d[N][N]={0};
12double dist(int a,int b)
13{
14return sqrt((zb[a].x-zb[b].x)*(zb[a].x-zb[b].x)+(zb[a].y-zb[b].y)*(zb[a].y-zb[b].y));
15}
16void input()
17{
18for(int i=1;i<=n;++i)
19       scanf("%lf%lf",&zb[i].x,&zb[i].y);
20}
21double dp(int i,int j)/*一开始误打成int，结果错了*/22{
23if(d[i][j]>0) 
24return d[i][j];
25if(i==n-1)
26       d[i][j]=dist(n-1,n)+dist(j,n);
27else28       d[i][j]=min(dp(i+1,j)+dist(i,i+1),dp(i+1,i)+dist(i+1,j));
29return d[i][j];
30}
31int main()
32{
33while(scanf("%d",&n)==1)
34    {
35        input();
36         memset(d,0,sizeof(d));
37         dp(2,1);
38         printf("%0.2lf\n",d[2][1]+dist(1,2));
39    }
40return0;
41 }