URAL(DP集）

这几天扫了一下URAL上面简单的DP  

第一题 简单递推

1225. Flags

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define LL long long
 7 LL dp[50][4];
 8 int main()
 9 {
10     int i,n;
11     scanf("%d",&n);
12     dp[1][1] = 1;dp[1][2] = 1;
13     for(i =2 ; i <= n ; i++)
14     {
15         dp[i][1] += dp[i-1][2]+dp[i-2][1];
16         dp[i][2] += dp[i-1][1]+dp[i-2][2];
17     }
18     LL ans = dp[n][1]+dp[n][2];
19     printf("%lld
",ans);
20     return 0;
21 }
View Cod

1031. Railway Tickets 

二重循环 加点限制

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define LL long long
 8 #define INF 100000000000
 9 LL dp[10010],ss[10010];
10 int main()
11 {
12     LL l1,l2,l3,c1,c2,c3;
13     int i,j,n,s,e,a,b;
14     cin>>l1>>l2>>l3>>c1>>c2>>c3;
15     cin>>n;
16     cin>>a>>b;
17     for(i = 2; i <= n ; i++)
18     scanf("%lld",&ss[i]);
19     s = min(a,b);
20     e = max(a,b);
21     dp[s] = 0;
22     for(i = s+1; i <= e ; i++)
23     {
24         dp[i] = INF;
25         for(j = i-1 ; j >=s ; j--)
26         {
27             if(ss[i]-ss[j]>l3)
28             break;
29             if(ss[i]-ss[j]>l2)
30             dp[i] = min(dp[i],dp[j]+c3);
31             else if(ss[i]-ss[j]>l1)
32             dp[i] = min(dp[i],dp[j]+c2);
33             else
34             dp[i] = min(dp[i],dp[j]+c1);
35         }
36     }
37     cout<<dp[e]<<endl;
38     return 0;
39 }
View Code

1073. Square Country

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 #define INF 0xfffffff
 9 #define N 60010
10 int dp[N];
11 int main()
12 {
13     int i,j,n;
14     scanf("%d",&n);
15     for(i = 1; i <= n ; i++)
16     {
17         int x = sqrt(i);
18         dp[i] = INF;
19         if(x*x==i)
20         dp[i] = 1;
21         else
22         {
23             for(j = 1; j <= x ; j++)
24             dp[i] = min(dp[i],dp[i-j*j]+1);
25         }
26     }
27     printf("%d
",dp[n]);
28     return 0;
29 }
View Code

1078. Segments

最长上升 加 路径 路径dfs回去就行 

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 int dp[510],path[510];
 8 struct node
 9 {
10     int x,y,id;
11 }p[510];
12 bool cmp(node a,node b)
13 {
14     if(a.y==b.y)
15     return a.x>b.x;
16     return a.y<b.y;
17 }
18 int o,g,flag;
19 void dfs(int u,int v)
20 {
21     int i;
22     if(flag)
23     return ;
24     path[v] = p[u].id;
25     if(v==dp[o])
26     {
27         flag = 1;
28         for(i = dp[o]; i > 1 ; i--)
29         printf("%d ",path[i]);
30         printf("%d
",path[1]);
31         return ;
32     }
33     for(i = 1; i < u ; i++)
34     if(p[i].x>p[u].x&&p[u].y>p[i].y)
35     {
36         if(dp[u]==dp[i]+1)
37         {
38             dfs(i,v+1);
39         }
40     }
41 }
42 int main()
43 {
44     int i,j,n;
45     scanf("%d",&n);
46     for(i = 1; i <= n ;i++)
47     {
48         scanf("%d%d",&p[i].x,&p[i].y);
49         p[i].id = i;
50     }
51     sort(p+1,p+n+1,cmp);
52     for(i = 1; i <= n ; i++)
53     {
54         dp[i] = 1;
55         for(j = 1; j < i ; j++)
56         if(p[j].x>p[i].x&&p[i].y>p[j].y)
57         dp[i] = max(dp[i],dp[j]+1);
58     }
59     int ans = 0;
60     for(i = 1; i <= n ; i++)
61     {
62         if(dp[i]>ans)
63         {
64             o = i;
65             ans = dp[i];
66         }
67     }
68     path[++g] = p[o].id;
69     printf("%d
",dp[o]);
70     dfs(o,1);
71     return 0;
72 }
View Code

1081. Binary Lexicographic Sequence

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define LL long long
 8 LL dp[50][2],sum[50],s;
 9 int p[50];
10 void init()
11 {
12     int i;
13     dp[1][0] = 1;
14     dp[1][1] = 1;
15     sum[1] = 2;
16     for(i = 2; i <=43 ; i++)
17     {
18         dp[i][0] = dp[i-1][0]+dp[i-1][1];
19         dp[i][1] = dp[i-1][0];
20         sum[i] = dp[i][0]+dp[i][1];
21     }
22 }
23 int main()
24 {
25     int i,j;
26     init();
27     int n;
28     scanf("%d%lld",&n,&s);
29     if(s>sum[n])
30     printf("-1
");
31     else
32     {
33         LL ss = s;
34         while(1)
35         {
36             for(i = n ; i >= 1 ; i--)
37             if(sum[i]<=ss)
38             {
39                 if(sum[i]==ss)
40                 {
41                     for(j = i ; j>=1 ; j-=2)
42                     p[j] = 1;
43                 }
44                 else
45                 {
46                     p[i+1] = 1;
47                 }
48                 ss-=sum[i];
49                 break;
50             }
51             if(i==0)
52             break;
53             if(ss==0)
54             break;
55         }
56         for(i = n; i >= 1 ; i--)
57         if(p[i])
58         printf("1");
59         else
60         printf("0");
61         puts("");
62     }
63     return 0;
64 }
View Code

1119. Metro

简单DP

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 #define INF 0xfffffff
 9 double dp[1010][1010];
10 int w[1010][1010];
11 int main()
12 {
13     int i,j,n,m,k,u,v;
14     scanf("%d%d",&n,&m);
15     scanf("%d",&k);
16     while(k--)
17     {
18         scanf("%d%d",&u,&v);
19         w[u][v] = 1;
20     }
21     for(i = 0; i <= n ; i++)
22         for(j = 0 ;j <= m ; j++)
23         dp[i][j] = INF;
24     dp[0][0] = 0;
25     for(i = 0; i <= n; i++)
26         for(j = 0; j <= m ; j++)
27         {
28             if(w[i][j]&&i>0&&j>0)
29             dp[i][j] = min(dp[i][j],dp[i-1][j-1]+100*sqrt(2.0));
30             if(i>0)
31             dp[i][j] = min(dp[i][j],dp[i-1][j]+100.0);
32             if(j>0)
33             dp[i][j] = min(dp[i][j],dp[i][j-1]+100.0);
34         }
35     int x = dp[n][m]+0.5;
36     printf("%d
",x);
37     return 0;
38 }
View Code

1152. False Mirrors

状压 好像写复杂了 时间跑得挺多 2s的限制 跑了1.1

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define INF 0xfffffff
 8 int dp[2][(1<<20)],s,a[21];
 9 int q[2][(1<<20)],p[101],sd[(1<<20)];
10 bool f[21][(1<<20)];
11 int main()
12 {
13     int i,j,n,o=0,g;
14     scanf("%d",&n);
15     for(j = 0 ; j < (1<<n) ; j++)
16     {
17         dp[1][j] = INF;
18         dp[0][j] = INF;
19     }
20     for(i = 1; i <= n ; i++)
21     {
22         scanf("%d",&a[i]);
23         s+=a[i];
24     }
25     for(i = 0 ; i < (1<<n) ; i++)
26     {
27         int ss=0;
28         for(j = 0 ; j < n ; j++)
29         if(i&(1<<j))
30         ss+=a[j+1];
31         ss = s-ss;
32         sd[i] = ss;
33     }
34     for(i = 0  ; i < n ; i++)
35     {
36         o++;
37         p[o] = (1<<i);q[1][o] = p[o];
38         o++;
39         p[o] = (1<<i)+(1<<(i+1)%n);q[1][o] = p[o];
40         o++;
41         p[o] = (1<<i)+(1<<(i+1)%n)+(1<<(i+2)%n);q[1][o] = p[o];
42     }
43     for(i = 1 ; i <= o ; i++)
44     {
45         dp[1][p[i]] = sd[p[i]];
46     }
47     int w = o;int ans = dp[1][(1<<n)-1];
48     for(i = 2; i <= n ; i++)
49     {
50         int tt=0;
51         for(j = 1; j <= o ; j++)
52         {
53             if(dp[(i-1)%2][q[(i-1)%2][j]]>ans)
54             continue;
55             for(g = 1 ; g <= w ; g++)
56             {
57                 if(q[(i-1)%2][j]&p[g])
58                 continue;
59                 int x = q[(i-1)%2][j]+p[g];
60                 dp[i%2][x] = min(dp[i%2][x],dp[(i-1)%2][q[(i-1)%2][j]]+sd[x]);
61                 if(!f[i][x])
62                 {
63                     f[i][x] = 1;
64                     tt++;
65                     q[i%2][tt] = x;
66                 }
67                 ans = min(ans,dp[i%2][(1<<n)-1]);
68             }
69         }
70         o = tt;
71     }
72     printf("%d
",ans);
73     return 0;
74 }
View Code

1167. Bicolored Horses

简单DP

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define INF 0xfffffff
 8 int s[510],a[510],dp[510][510];
 9 int main()
10 {
11     int i,j,n,k;
12     scanf("%d%d",&n,&k);
13     for(i = 1; i <= n ; i++)
14     {
15         scanf("%d",&a[i]);
16         s[i]+=s[i-1]+a[i];
17     }
18     for(i = 1; i <= k ;i++)
19         for(j =1 ; j <= n ; j++)
20         dp[i][j] = INF;
21     for(i = 1; i <= n-(k-1) ; i++)
22     dp[1][i] = s[i]*(i-s[i]);
23     for(i = 2; i <= k ; i++)
24     {
25         for(j = i ; j <= n-(k-i) ; j++)
26         {
27             dp[i][j] = INF;
28             for(int g = i-1 ; g < j ; g++)
29             {
30                 int o = s[j]-s[g];
31                 dp[i][j] = min(dp[i][j],dp[i-1][g]+o*(j-g-o));
32             }
33         }
34     }
35     printf("%d
",dp[k][n]);
36     return 0;
37 }
View Code

1203. Scientific Conference

以前贪心可过的题 数据加大后DP O（n)可过

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 int dp[30010],w[30010];
 8 struct node
 9 {
10     int s,e;
11 }p[100010];
12 bool cmp(node a,node b)
13 {
14     if(a.e==b.e)
15     return a.s<b.s;
16     return a.e<b.e;
17 }
18 int main()
19 {
20     int i,n;
21     scanf("%d",&n);
22     for(i = 1; i <= n ; i++)
23     scanf("%d%d",&p[i].s,&p[i].e);
24     sort(p+1,p+n+1,cmp);
25     for(i= 1; i <= n ; i++)
26     {
27         dp[p[i].e] = 1;
28         w[p[i].e] = p[i].s;
29     }
30     int maxz=p[n].e;
31     for(i = 1; i <= maxz ; i++)
32     {
33         if(w[i])
34         dp[i] = max(dp[i],dp[w[i]-1]+1);
35         dp[i] = max(dp[i],dp[i-1]);
36     }
37     printf("%d
",dp[maxz]);
38     return 0;
39 }
View Code

1260. Nudnik Photographer

这题。。以前做过 又卡了我一次 

分三种情况 dp[n] = dp[n-1]+dp[n-3]+1;

12。。。。。dp[n-1]

1324.........dp[n-3]

13579.....8642 这种就一种情况

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define LL long long
 8 LL dp[60];
 9 int main()
10 {
11     int i,n;
12     scanf("%d",&n);
13     dp[1] =1;
14     dp[2]= 1;
15     dp[3] = 2;
16     for(i = 4 ; i <= n ; i++)
17     dp[i] = dp[i-1]+dp[i-3]+1;
18     printf("%lld
",dp[n]);
19     return 0;
20 }
View Code

1303. Minimal Coverage

以m进行递推 因为没解的时候 还输出路径了 RE了N久。。

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define INF 0xfffffff
 8 int dp[50100],f[50010],q[50010];
 9 int path[50100];
10 struct node
11 {
12     int sx,x,y;
13 }p[100010];
14 int o;
15 int main()
16 {
17     int i,j,m,x,y;
18     scanf("%d",&m);
19     memset(f,-1,sizeof(f));
20     for(i = 1 ; i <= m ; i++)
21     dp[i] = INF;
22     dp[0] = 0;
23     while(scanf("%d%d",&x,&y)!=EOF)
24     {
25         if(x==0&&y==0)
26         break;
27         if(y>0&&x<m)
28         {
29             o++;
30             p[o].sx = x;
31             p[o].y = y;
32             if(x<0)
33             x=0;
34             p[o].x = x;
35             if(f[y]==-1||f[y]>x)
36             {
37                 f[y] = x;
38                 q[y] = o;
39             }
40         }
41     }
42     for(i = 1; i <= m ; i++)
43     {
44         if(f[i]!=-1)
45         {
46             if(dp[i]>dp[f[i]]+1)
47             {
48                 dp[i] = dp[f[i]]+1;
49                 path[dp[i]] = q[i];
50                 for(j = f[i] ; j <= i ; j++)
51                 dp[j] = min(dp[j],dp[i]);
52             }
53         }
54     }
55     for(i = 1 ; i <= o ; i++)
56     {
57         if(p[i].x<m&&p[i].y>m)
58         {
59             if(dp[m]>dp[p[i].x]+1)
60             {
61                 dp[m] = dp[p[i].x]+1;
62                 path[dp[m]] = i;
63             }
64         }
65     }
66     if(dp[m]==INF)
67     puts("No solution");
68     else
69     {
70         printf("%d
",dp[m]);
71         for(i = 1; i <= dp[m] ; i++)
72         printf("%d %d
",p[path[i]].sx,p[path[i]].y);
73     }
74     return 0;
75 }
View Code

1353. Milliard Vasya's Function

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define LL long long
 8 LL dp[12][90];
 9 int main()
10 {
11     int i,j,g,s;
12     scanf("%d",&s);
13     for(int p = 1; p <= 9 ; p++)
14         dp[1][p] = 1;
15     LL ans=dp[1][s];
16     for(i = 2;  i <= 9 ; i++)
17     {
18         memset(dp,0,sizeof(dp));
19         for(int p = 1; p <= 9 ; p++)
20         dp[1][p] = 1;
21         for(int o = 2 ; o <= i ; o++)
22         for(j = 0 ; j <= s ; j++)
23         {
24             if(o==10)
25             {
26                 dp[o][j]+=dp[o-1][j-1];
27                 continue;
28             }
29             for(g = 0 ; g <= 9 ; g++)
30             {
31                 if(g>j)
32                 continue;
33                 dp[o][j] += dp[o-1][j-g];
34             }
35         }
36         ans+=dp[i][s];
37     }
38     if(s==1)
39     ans++;
40     printf("%lld
",ans);
41     return 0;
42 }
View Code

1586. Threeprime Numbers

这题。。初始化数组里面一个顺序写反了 纠结了半天 三维保存两位的状态

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define LL long long
 8 #define mod 1000000009
 9 LL dp[10010][12][12];
10 int p[1010];
11 void init()
12 {
13     int i,j,x=0;
14     for(i = 3; i < 1000 ; i++)
15     {
16         for(j = 2 ;j < i ; j++)
17         if(i%j==0)
18         break;
19         if(j==i)
20         {
21             p[i] = 1;
22         }
23     }
24 }
25 int main()
26 {
27     int i,j,n,o,g;
28     init();
29     scanf("%d",&n);
30     for(i = 100 ; i <= 999 ; i++)
31     {
32         if(p[i])
33         {
34             dp[3][(i/10)%10][i/100]++;
35         }
36     }
37     for(i = 4 ; i <= n ;i++)
38     {
39         for(j = 1 ; j <= 9 ; j++)
40         {
41             for(g = 0 ; g <= 9 ; g++)
42             {
43                 for(o = 0 ; o <= 9 ; o++)
44                 {
45                     int x1 = j*100+g*10+o;
46                     if(p[x1])
47                     {
48                         dp[i][g][j] = (dp[i][g][j]+dp[i-1][o][g])%mod;
49                     }
50                 }
51             }
52         }
53     }
54     LL ans=0;
55     for(j = 1 ; j <= 9 ; j++)
56     for(i = 0; i <= 9 ; i++)
57     {
58         ans = (ans+dp[n][i][j])%mod;
59     }
60     printf("%lld
",ans);
61     return 0;
62 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/shangyu/p/3306077.html