训练第三周之dp习题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],dp[100005];
int rem[100005],s,k;
int main()
{
int t,n,i,Max,j,m;
scanf("%d",&t);
k=1;
do
{
if(k>1)
printf("n");
scanf("%d",&n);
memset(dp,0,sizeof(dp));
s=1;
rem[1]=1;
m=j=1;//j记录最大和子串的开始，m记录结尾
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Max=a[1];
///记录最大值
for(i=1;i<=n;i++)
{
if(dp[i-1]>=0)
{
dp[i]=dp[i-1]+a[i];//前i个元素中连续子串最大和
if(Max==dp[i])//只有该最大值第一次出现记录，以后出现不记录
if(rem[1]==j)
{
m=i;
}
if(Max<dp[i]){
Max=dp[i];
j=rem[1];
m=i;
}
rem[s++]=i;//记录最大和子串
//printf("%d %dn",j,m);
}
else
{
dp[i]=a[i];
s=1;
rem[s++]=i;
if(Max<a[i])
{
Max=a[i];
j=i;
m=i;
}
//printf("%d %dn",s,rem[s-1]);
}
}
/*for(i=0;i<s;i++)
printf("%dn",rem[i]);*/
if(j!=m){
printf("Case %d:n",k);
printf("%d %d %dn",Max,j,m);
}
else//j等于m说明最大值子串只有一个数
{
for(i=1;i<=n;i++)
if(Max==a[i])
break;
printf("Case %d:n",k);
printf("%d %d %dn",Max,i,i);
}
k++;
}while(k<=t);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
long long f[6000];/*第i项总可以由前i-1项中的某一项与2,3,5,7相乘得到，且为大于第i-1项的最小值*/
int way[4]={2,3,5,7};
int main()
{
int i,j,k,t,n;
memset(f,-1,sizeof(f));
f[1]=1;
for(i=2;i<=5842;i++)
{
for(j=0;j<4;j++)
for(k=i-1;k>=1;k--)
{
if(f[k]*way[j]<=f[i-1])
break;
if(f[k]*way[j]<f[i]||f[i]<0)
f[i]=f[k]*way[j];
}
}
//printf("%dn",f[1000]);
while(scanf("%d",&n)!=EOF&&n)
{
printf("The %d",n);
if(n%10==1&&n%100!=11){printf("st humble number is %d.n",f[n]);continue;}
if(n%10==2&&n%100!=12){printf("nd humble number is %d.n",f[n]);continue;}
if(n%10==3&&n%100!=13){printf("rd humble number is %d.n",f[n]);continue;}
printf("th humble number is %d.n",f[n]);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
int s;
int f[10005];
int main()
{
int n,i,j,flag,m,t,k;
while(scanf("%d",&n)!=EOF)
{
s=0;
memset(f,0,sizeof(f));
for(i=0;i<n;i++)
{
scanf("%d",&m);
flag=0;
k=1;
t=2e9;
for(j=1;j<=s;j++)
{
if(f[j]>=m)
{
flag=1;
if(t>f[j]-m)
{
t=f[j]-m;
k=j;
}
}
}
if(flag)
{
f[k]=m;
}
else
{
f[++s]=m;
}
}
printf("%dn",s);
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct dimensions
{
int x,y,z;
}dim[100];
int dp[100];
int t=0;
typedef struct dimensions d;
bool cmp(d a,d b)
{
if(a.x==b.x)
return a.y>b.y;
return a.x>b.x;
}
int main()
{
int n,i,j,a,b,c,maxdp;
while(cin>>n&&n)
{
j=0;
for(i=0;i<n;i++)//将每种积木变成三种只有一个底面一个高的积木，分别存入dim[j]到dim[j+2]
{
cin>>a>>b>>c;
dim[j].x=min(a,b);
dim[j].y=max(a,b);
dim[j].z=c;
dim[j+1].x=min(a,c);
dim[j+1].y=max(a,c);
dim[j+1].z=b;
dim[j+2].x=min(b,c);
dim[j+2].y=max(b,c);
dim[j+2].z=a;
j+=3;
}
n=j;
sort(dim,dim+n,cmp);//将积木按底面从大到小排序
maxdp=0;
//cout<<n<<endl;
for(i=0;i<n;i++)
{
dp[i]=dim[i].z;
for(j=i-1;j>=0;j--)
{
if(dim[j].x>dim[i].x&&dim[j].y>dim[i].y)
if(dp[j]+dim[i].z>dp[i])
dp[i]=dp[j]+dim[i].z;
}
if(dp[i]>maxdp)//dp[i]为放第i个积木能达到的最大高度
maxdp=dp[i];
}
cout<<"Case "<<++t<<":";
cout<<" maximum height = "<<maxdp<<endl;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[50];//从n到i的次数
int main()
{
int n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
{
memset(dp,0,sizeof(dp));
dp[n]=1;
for(i=n;i>=1;i--)
{
for(j=1;j<=m;j++)
{
if(i>=j)
dp[i-j]=dp[i]+dp[i-j];
}
}
printf("%dn",dp[1]);
}
return 0;
}