复习一下一直不太懂的dp.
dp博大精深,路还长着呢
第一题;http://acm.hdu.edu.cn/showproblem.php?pid=2084
从下往上就是水题
#include<cstdio>
using namespace std;
int max(int x,int y)
{
if (x<y) return y;
else return x;
}
int main()
{
int t,n,yj[][],i,j;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
for (i=;i<=n;i++)
{
for (j=;j<=i;j++)
scanf("%d",&yj[i][j]);
}
for (i=n-;i>=;i--){
for (j=;j<=i;j++)
yj[i][j]+=max(yj[i+][j],yj[i+][j+]);
}
printf("%d\n",yj[][]);
}
return ;
}
第二题;http://acm.hdu.edu.cn/showproblem.php?pid=1231
与贪心有点像,样例能过基本就能A
#include<cstdio>
using namespace std;
int a[];
int main()
{
int n,sum,mn,sx,sy,x,i;
while (~scanf("%d",&n))
{
if (!n) break;
int flag=;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]>=) flag=;
}
if (!flag)
{
printf("0 %d %d\n",a[],a[n]);
continue;
}
sum=,mn=-;
sx=sy=x=;
for (i=;i<=n;i++)
{
sum+=a[i];
if (sum<)
{
while (a[i]<&&i<=n)
i++;
if (i<=n)
{
x=i;sum=a[i];
}
else break;
}
if (sum>mn)
{
sy=i;
sx=x;
mn=sum;
}
}
printf("%d %d %d\n",mn,a[sx],a[sy]);
}
return ;
}
第三题;http://acm.hdu.edu.cn/showproblem.php?pid=1003
和第二题差不多,只不过变成了输出头和尾的序号,注意这题对都是负数没有特别输出了,要求不同
#include<cstdio>
using namespace std;
int a[];
int main()
{
int t,ans=,i,n,sum,sx,sy,x;
scanf("%d",&t);
while (t--)
{
scanf("%d",&n);
int flag=,mx=-;
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
if (mx<a[i]) mx=a[i],sx=sy=i;
if (a[i]>=) flag=;
}
printf("Case %d:\n",ans++);
if (flag==)
{
printf("%d %d %d\n",mx,sx,sy);
if (t!=) printf("\n");
continue;
}
sum=,sx=,sy=,x=;
int mn=-;
for (i=;i<=n;i++)
{
sum+=a[i];
if (sum<)
{
while (a[i]<&&i<=n)
i++;
if (i<=n)
{
x=i;sum=a[i];
}
else break;
}
if (mn<sum)
{
sx=x;
sy=i;
mn=sum;
}
}
printf("%d %d %d\n",mn,sx,sy);
if (t!=) printf("\n");
}
return ;
}
第四题;http://acm.hdu.edu.cn/showproblem.php?pid=1087
求递增序列的最大和,有个题意设置的坑就是这个递增序列可以不连续
#include<stdio.h>
int main()
{
int i,j,n,max,t;
int a[];
int sum[];
while(~scanf("%d",&n))
{
if (n==)
break;
for(i=;i<n;i++)
{
scanf("%d",&a[i]);
sum[i]=a[i];
}
t=;
for(j=;j<n;j++)
{
max=;
for(i=;i<=j;i++)
{
if(a[i]<a[j])
{
if(sum[i]>max)
max=sum[i];
}
}
sum[j]=max+a[j];
if (sum[j]>t)
t=sum[j];
}
printf("%d\n",t);
}
return ;
}