简单DP入门四连发

复习一下一直不太懂的dp.

dp博大精深,路还长着呢

第一题;http://acm.hdu.edu.cn/showproblem.php?pid=2084

从下往上就是水题

 1 #include<cstdio>
 2 using namespace std;
 3 int max(int x,int y)
 4 {
 5     if (x<y) return y;
 6     else return x;
 7 }
 8 int main()
 9 {
10     int t,n,yj[101][101],i,j;
11     scanf("%d",&t);
12     while (t--)
13     {
14         scanf("%d",&n);
15         for (i=1;i<=n;i++)
16         {
17             for (j=1;j<=i;j++)
18                 scanf("%d",&yj[i][j]);
19         }
20         for (i=n-1;i>=1;i--){
21             for (j=1;j<=i;j++)
22                 yj[i][j]+=max(yj[i+1][j],yj[i+1][j+1]);
23         }
24         printf("%d
",yj[1][1]);
25     }
26     return 0;
27 }

第二题;http://acm.hdu.edu.cn/showproblem.php?pid=1231

与贪心有点像,样例能过基本就能A

 1 #include<cstdio>
 2 using namespace std;
 3 int a[10001];
 4 int main()
 5 {
 6     int n,sum,mn,sx,sy,x,i;
 7     while (~scanf("%d",&n))
 8     {
 9         if (!n) break;
10         int flag=0;
11         for (i=1;i<=n;i++)
12         {
13             scanf("%d",&a[i]);
14             if (a[i]>=0) flag=1;
15         }
16         if (!flag)
17         {
18             printf("0 %d %d
",a[1],a[n]);
19             continue;
20         }
21         sum=0,mn=-100000;
22         sx=sy=x=1;
23         for (i=1;i<=n;i++)
24         {
25             sum+=a[i];
26             if (sum<0)
27             {
28                 while (a[i]<0&&i<=n)
29                     i++;
30                 if (i<=n)
31                 {
32                     x=i;sum=a[i];
33                 }
34                 else break;
35             }
36             if (sum>mn)
37             {
38                 sy=i;
39                 sx=x;
40                 mn=sum;
41             }
42         }
43         printf("%d %d %d
",mn,a[sx],a[sy]);
44     }
45     return 0;
46 }

第三题;http://acm.hdu.edu.cn/showproblem.php?pid=1003

和第二题差不多,只不过变成了输出头和尾的序号,注意这题对都是负数没有特别输出了,要求不同

 1 #include<cstdio>
 2 using namespace std;
 3 int a[100001];
 4 int main()
 5 {
 6     int t,ans=1,i,n,sum,sx,sy,x;
 7     scanf("%d",&t);
 8     while (t--)
 9     {
10         scanf("%d",&n);
11         int flag=0,mx=-100000;
12         for (i=1;i<=n;i++)
13         {
14             scanf("%d",&a[i]);
15             if (mx<a[i]) mx=a[i],sx=sy=i;
16             if (a[i]>=0) flag=1;
17         }
18         printf("Case %d:
",ans++);
19         if (flag==0)
20         {
21             printf("%d %d %d
",mx,sx,sy);
22             if (t!=0) printf("
");
23             continue;
24         }
25         sum=0,sx=1,sy=1,x=1;
26         int mn=-100000;
27         for (i=1;i<=n;i++)
28         {
29              sum+=a[i];
30              if (sum<0)
31              {
32                  while (a[i]<0&&i<=n)
33                     i++;
34                  if (i<=n)
35                  {
36                      x=i;sum=a[i];
37                  }
38                  else break;
39              }
40              if (mn<sum)
41              {
42                  sx=x;
43                  sy=i;
44                  mn=sum;
45              }
46         }
47         printf("%d %d %d
",mn,sx,sy);
48         if (t!=0) printf("
");
49     }
50     return 0;
51 }

第四题;http://acm.hdu.edu.cn/showproblem.php?pid=1087

求递增序列的最大和,有个题意设置的坑就是这个递增序列可以不连续

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int i,j,n,max,t;
 5     int a[1001];
 6     int sum[1001];
 7     while(~scanf("%d",&n))
 8     {
 9         if (n==0)
10             break;
11         for(i=0;i<n;i++)
12         {
13             scanf("%d",&a[i]);
14             sum[i]=a[i];
15         }
16         t=0;
17         for(j=0;j<n;j++)
18         {
19             max=0;
20             for(i=0;i<=j;i++)
21             {
22                 if(a[i]<a[j])
23                 {
24                     if(sum[i]>max)
25                         max=sum[i];
26                 }
27             }
28             sum[j]=max+a[j];
29             if (sum[j]>t)
30                 t=sum[j];
31         }
32         printf("%d
",t);
33     }
34     return 0;
35 }