Training:动态规划

HDU 2084:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=23620
数字三角形,简单DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=110;
int g[maxn][maxn],d[maxn][maxn];
int main(){
int t;scanf("%d",&t);
while(t--){
memset(d,0,sizeof(d));
int n;scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
scanf("%d",&g[i][j]);
for(int i=n;i>0;--i)
for(int j=1;j<=i;++j)
d[i][j]=max(d[i+1][j],d[i+1][j+1])+g[i][j];
printf("%d\n",d[1][1]);
}
return 0;
}

HDU 1176:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=22018
给出馅饼掉落的时间和位置,每次只能移动一格,求最多接到多少个馅饼。简单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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int d[maxn][13],g[maxn][13];
int main(){
int n;
while(~scanf("%d",&n)&&n){
memset(d,0,sizeof(d));
memset(g,0,sizeof(g));
int maxt=0;
for(int i=1;i<=n;++i){
int p,t;
scanf("%d%d",&p,&t);
++g[t][p+1],maxt=max(maxt,t);
}
for(int i=maxt;i>=0;--i)
for(int j=1;j<=11;++j)
d[i][j]=max(max(d[i+1][j-1],d[i+1][j]),d[i+1][j+1])+g[i][j];
printf("%d\n",d[0][6]);
}
return 0;
}

HDU 1087:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17613
求最大上升子序列的和,数据量小,可以 O ( n 2 ) 算法DP求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010;
int a[maxn],d[maxn];
int main(){
int n;
while(~scanf("%d",&n)&&n){
int ans=-(0x3f3f3f3f);
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i)
scanf("%d",&a[i]),d[i]=a[i],ans=max(ans,a[i]);
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(a[i]<a[j])
d[j]=max(d[j],d[i]+a[j]),ans=max(ans,d[j]);
printf("%d\n",ans);
}
return 0;
}

HDU 1421:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17361
给出每个物品的重量 a i ,每次可以搬两件,搬物品 a i 和 a j 的疲劳值为 p = a 2 i + a 2
j ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ √ 。给出物品数 n 、要搬的次数 k 、 n 件物品的重量,输出最小疲劳值。
二维DP,排序之后,求相邻两物品重量差 b i , d [ i ] [ j ] = m i n ( d [ i −
1 ] [ j − 2 ] + b [ j − 1 ] , d [ i ] [ j − 1 ] ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2010;
int a[maxn],b[maxn],d[maxn/2][maxn];
int main(){
int n,k;
while(~scanf("%d%d",&n,&k)){
memset(d,0x3f,sizeof(d));
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1;i<n;++i) b[i]=(a[i]-a[i+1])*(a[i]-a[i+1]);
for(int i=0;i<=k;++i){
for(int j=2*i;j<=n;++j)
if(!i) d[i][j]=0;
else d[i][j]=min(d[i-1][j-2]+b[j-1],d[i][j-1]);
}
printf("%d\n",d[k][n]);
}
return 0;
}

HDU 1058:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17350
类似于紫书上丑数的生成,统计当前最大数因子中2、3、5、7的个数。然后每次生成最小的数。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5900;
int ans[maxn];
int main(){
ans[1]=1;
int a=1,b=1,c=1,d=1;
for(int i=2;i<=5842;++i){
ans[i]=min(2*ans[a],min(3*ans[b],min(5*ans[c],7*ans[d])));
if(ans[i]==2*ans[a]) ++a;
if(ans[i]==3*ans[b]) ++b;
if(ans[i]==5*ans[c]) ++c;
if(ans[i]==7*ans[d]) ++d;
}
int n;
while(~scanf("%d",&n)&&n){
printf("The %d",n);
if(n%10==1&&n%100!=11) printf("st");
else if(n%10==2&&n%100!=12) printf("nd");
else if(n%10==3&&n%100!=13) printf("rd");
else printf("th");
printf(" humble number is %d.\n",ans[n]);
}
return 0;
}

HDU 1160:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30429
给出 n 个老鼠的体重 w 和速度 v ,求最长的老鼠 w 增大, v 减小的序列长度,并输出这个序列。
对 w 排序后,对 v 求LIS。

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
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=1010;
int d[maxn],pre[maxn];
struct node{
int w,v,id;
bool operator < (const node& rhs) const {
return w==rhs.w?v<rhs.v:w<rhs.w;
}
}a[maxn];
int main(){
int n=0;
while(~scanf("%d%d",&a[n+1].w,&a[n+1].v)) ++n,a[n].id=n,d[n]=1;
sort(a+1,a+n+1);
int best=1,pos=1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(a[i].w<a[j].w&&a[i].v>a[j].v){
if(d[i]+1>d[j]) d[j]=d[i]+1,pre[a[j].id]=a[i].id;
if(d[j]>best){
best=d[j];
pos=a[j].id;
}
}
printf("%d\n",best);
stack<int> ans;
while(pos) ans.push(pos),pos=pre[pos];
while(!ans.empty()) printf("%d\n",ans.top()),ans.pop();
return 0;
}

HDU 1159:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=30429
求两个字符串的LCS长度。 O ( n 2 ) 的DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=550;
int d[maxn][maxn];
char s1[maxn],s2[maxn];
int main(){
while(~scanf("%s%s",s1+1,s2+1)){
memset(d,0,sizeof(d));
int l1=(int)strlen(s1+1),l2=(int)strlen(s2+1);
for(int i=1;i<=l1;++i)
for(int j=1;j<=l2;++j){
if(s1[i]==s2[j]) d[i][j]=d[i-1][j-1]+1;
else d[i][j]=max(d[i-1][j],d[i][j-1]);
}
printf("%d\n",d[l1][l2]);
}
return 0;
}

HDU 1003:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=15514
求数列最大连续和,简单DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
const int inf=0x3f3f3f3f;
int main(){
int t,tt=0;scanf("%d",&t);
while(t--){
int n;scanf("%d",&n);
int sum=-inf,best=-inf,st=1,ed=1,cur=1;
for(int i=1;i<=n;i++){
if(sum<0) cur=i,sum=0;
int k;scanf("%d",&k);
sum+=k;
if(best<sum) best=sum,st=cur,ed=i;
}
printf("Case %d:\n%d %d %d\n",++tt,best,st,ed);
if(t) printf("\n");
}
return 0;
}

HDU 4540:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=37953
给出所有时刻地鼠的位置,共有 m ≤ 500 个位置, O ( m 2 ) ,求简单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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int d[25][15],g[25][15];
int main(){
int n,k;
while(~scanf("%d%d",&n,&k)){
memset(g,0,sizeof(g));
memset(d,0x3f,sizeof(d));
for(int i=1;i<=n;++i)
for(int j=1;j<=k;++j)
scanf("%d",&g[i][j]);
int ans=0x3f3f3f3f;
for(int i=1;i<=n;++i)
for(int j=1;j<=k;++j){
if(i==1) d[i][j]=0;
else for(int l=1;l<=k;++l)
d[i][j]=min(d[i][j],d[i-1][l]+abs(g[i][j]-g[i-1][l]));
if(i==n) ans=min(ans,d[i][j]);
}
printf("%d\n",ans);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。