这几天扫了一下URAL上面简单的DP
第一题 简单递推
1225. Flags
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL dp[][];
int main()
{
int i,n;
scanf("%d",&n);
dp[][] = ;dp[][] = ;
for(i = ; i <= n ; i++)
{
dp[i][] += dp[i-][]+dp[i-][];
dp[i][] += dp[i-][]+dp[i-][];
}
LL ans = dp[n][]+dp[n][];
printf("%lld\n",ans);
return ;
}
View Cod
1031. Railway Tickets
二重循环 加点限制
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
#define INF 100000000000
LL dp[],ss[];
int main()
{
LL l1,l2,l3,c1,c2,c3;
int i,j,n,s,e,a,b;
cin>>l1>>l2>>l3>>c1>>c2>>c3;
cin>>n;
cin>>a>>b;
for(i = ; i <= n ; i++)
scanf("%lld",&ss[i]);
s = min(a,b);
e = max(a,b);
dp[s] = ;
for(i = s+; i <= e ; i++)
{
dp[i] = INF;
for(j = i- ; j >=s ; j--)
{
if(ss[i]-ss[j]>l3)
break;
if(ss[i]-ss[j]>l2)
dp[i] = min(dp[i],dp[j]+c3);
else if(ss[i]-ss[j]>l1)
dp[i] = min(dp[i],dp[j]+c2);
else
dp[i] = min(dp[i],dp[j]+c1);
}
}
cout<<dp[e]<<endl;
return ;
}
1073. Square Country
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define INF 0xfffffff
#define N 60010
int dp[N];
int main()
{
int i,j,n;
scanf("%d",&n);
for(i = ; i <= n ; i++)
{
int x = sqrt(i);
dp[i] = INF;
if(x*x==i)
dp[i] = ;
else
{
for(j = ; j <= x ; j++)
dp[i] = min(dp[i],dp[i-j*j]+);
}
}
printf("%d\n",dp[n]);
return ;
}
1078. Segments
最长上升 加 路径 路径dfs回去就行
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[],path[];
struct node
{
int x,y,id;
}p[];
bool cmp(node a,node b)
{
if(a.y==b.y)
return a.x>b.x;
return a.y<b.y;
}
int o,g,flag;
void dfs(int u,int v)
{
int i;
if(flag)
return ;
path[v] = p[u].id;
if(v==dp[o])
{
flag = ;
for(i = dp[o]; i > ; i--)
printf("%d ",path[i]);
printf("%d\n",path[]);
return ;
}
for(i = ; i < u ; i++)
if(p[i].x>p[u].x&&p[u].y>p[i].y)
{
if(dp[u]==dp[i]+)
{
dfs(i,v+);
}
}
}
int main()
{
int i,j,n;
scanf("%d",&n);
for(i = ; i <= n ;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
p[i].id = i;
}
sort(p+,p+n+,cmp);
for(i = ; i <= n ; i++)
{
dp[i] = ;
for(j = ; j < i ; j++)
if(p[j].x>p[i].x&&p[i].y>p[j].y)
dp[i] = max(dp[i],dp[j]+);
}
int ans = ;
for(i = ; i <= n ; i++)
{
if(dp[i]>ans)
{
o = i;
ans = dp[i];
}
}
path[++g] = p[o].id;
printf("%d\n",dp[o]);
dfs(o,);
return ;
}
1081. Binary Lexicographic Sequence
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
LL dp[][],sum[],s;
int p[];
void init()
{
int i;
dp[][] = ;
dp[][] = ;
sum[] = ;
for(i = ; i <= ; i++)
{
dp[i][] = dp[i-][]+dp[i-][];
dp[i][] = dp[i-][];
sum[i] = dp[i][]+dp[i][];
}
}
int main()
{
int i,j;
init();
int n;
scanf("%d%lld",&n,&s);
if(s>sum[n])
printf("-1\n");
else
{
LL ss = s;
while()
{
for(i = n ; i >= ; i--)
if(sum[i]<=ss)
{
if(sum[i]==ss)
{
for(j = i ; j>= ; j-=)
p[j] = ;
}
else
{
p[i+] = ;
}
ss-=sum[i];
break;
}
if(i==)
break;
if(ss==)
break;
}
for(i = n; i >= ; i--)
if(p[i])
printf("");
else
printf("");
puts("");
}
return ;
}
1119. Metro
简单DP
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define INF 0xfffffff
double dp[][];
int w[][];
int main()
{
int i,j,n,m,k,u,v;
scanf("%d%d",&n,&m);
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&u,&v);
w[u][v] = ;
}
for(i = ; i <= n ; i++)
for(j = ;j <= m ; j++)
dp[i][j] = INF;
dp[][] = ;
for(i = ; i <= n; i++)
for(j = ; j <= m ; j++)
{
if(w[i][j]&&i>&&j>)
dp[i][j] = min(dp[i][j],dp[i-][j-]+*sqrt(2.0));
if(i>)
dp[i][j] = min(dp[i][j],dp[i-][j]+100.0);
if(j>)
dp[i][j] = min(dp[i][j],dp[i][j-]+100.0);
}
int x = dp[n][m]+0.5;
printf("%d\n",x);
return ;
}
1152. False Mirrors
状压 好像写复杂了 时间跑得挺多 2s的限制 跑了1.1
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0xfffffff
int dp[][(<<)],s,a[];
int q[][(<<)],p[],sd[(<<)];
bool f[][(<<)];
int main()
{
int i,j,n,o=,g;
scanf("%d",&n);
for(j = ; j < (<<n) ; j++)
{
dp[][j] = INF;
dp[][j] = INF;
}
for(i = ; i <= n ; i++)
{
scanf("%d",&a[i]);
s+=a[i];
}
for(i = ; i < (<<n) ; i++)
{
int ss=;
for(j = ; j < n ; j++)
if(i&(<<j))
ss+=a[j+];
ss = s-ss;
sd[i] = ss;
}
for(i = ; i < n ; i++)
{
o++;
p[o] = (<<i);q[][o] = p[o];
o++;
p[o] = (<<i)+(<<(i+)%n);q[][o] = p[o];
o++;
p[o] = (<<i)+(<<(i+)%n)+(<<(i+)%n);q[][o] = p[o];
}
for(i = ; i <= o ; i++)
{
dp[][p[i]] = sd[p[i]];
}
int w = o;int ans = dp[][(<<n)-];
for(i = ; i <= n ; i++)
{
int tt=;
for(j = ; j <= o ; j++)
{
if(dp[(i-)%][q[(i-)%][j]]>ans)
continue;
for(g = ; g <= w ; g++)
{
if(q[(i-)%][j]&p[g])
continue;
int x = q[(i-)%][j]+p[g];
dp[i%][x] = min(dp[i%][x],dp[(i-)%][q[(i-)%][j]]+sd[x]);
if(!f[i][x])
{
f[i][x] = ;
tt++;
q[i%][tt] = x;
}
ans = min(ans,dp[i%][(<<n)-]);
}
}
o = tt;
}
printf("%d\n",ans);
return ;
}
1167. Bicolored Horses
简单DP
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0xfffffff
int s[],a[],dp[][];
int main()
{
int i,j,n,k;
scanf("%d%d",&n,&k);
for(i = ; i <= n ; i++)
{
scanf("%d",&a[i]);
s[i]+=s[i-]+a[i];
}
for(i = ; i <= k ;i++)
for(j = ; j <= n ; j++)
dp[i][j] = INF;
for(i = ; i <= n-(k-) ; i++)
dp[][i] = s[i]*(i-s[i]);
for(i = ; i <= k ; i++)
{
for(j = i ; j <= n-(k-i) ; j++)
{
dp[i][j] = INF;
for(int g = i- ; g < j ; g++)
{
int o = s[j]-s[g];
dp[i][j] = min(dp[i][j],dp[i-][g]+o*(j-g-o));
}
}
}
printf("%d\n",dp[k][n]);
return ;
}
1203. Scientific Conference
以前贪心可过的题 数据加大后DP O(n)可过
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
int dp[],w[];
struct node
{
int s,e;
}p[];
bool cmp(node a,node b)
{
if(a.e==b.e)
return a.s<b.s;
return a.e<b.e;
}
int main()
{
int i,n;
scanf("%d",&n);
for(i = ; i <= n ; i++)
scanf("%d%d",&p[i].s,&p[i].e);
sort(p+,p+n+,cmp);
for(i= ; i <= n ; i++)
{
dp[p[i].e] = ;
w[p[i].e] = p[i].s;
}
int maxz=p[n].e;
for(i = ; i <= maxz ; i++)
{
if(w[i])
dp[i] = max(dp[i],dp[w[i]-]+);
dp[i] = max(dp[i],dp[i-]);
}
printf("%d\n",dp[maxz]);
return ;
}
1260. Nudnik Photographer
这题。。以前做过 又卡了我一次
分三种情况 dp[n] = dp[n-1]+dp[n-3]+1;
12。。。。。dp[n-1]
1324.........dp[n-3]
13579.....8642 这种就一种情况
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
LL dp[];
int main()
{
int i,n;
scanf("%d",&n);
dp[] =;
dp[]= ;
dp[] = ;
for(i = ; i <= n ; i++)
dp[i] = dp[i-]+dp[i-]+;
printf("%lld\n",dp[n]);
return ;
}
1303. Minimal Coverage
以m进行递推 因为没解的时候 还输出路径了 RE了N久。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define INF 0xfffffff
int dp[],f[],q[];
int path[];
struct node
{
int sx,x,y;
}p[];
int o;
int main()
{
int i,j,m,x,y;
scanf("%d",&m);
memset(f,-,sizeof(f));
for(i = ; i <= m ; i++)
dp[i] = INF;
dp[] = ;
while(scanf("%d%d",&x,&y)!=EOF)
{
if(x==&&y==)
break;
if(y>&&x<m)
{
o++;
p[o].sx = x;
p[o].y = y;
if(x<)
x=;
p[o].x = x;
if(f[y]==-||f[y]>x)
{
f[y] = x;
q[y] = o;
}
}
}
for(i = ; i <= m ; i++)
{
if(f[i]!=-)
{
if(dp[i]>dp[f[i]]+)
{
dp[i] = dp[f[i]]+;
path[dp[i]] = q[i];
for(j = f[i] ; j <= i ; j++)
dp[j] = min(dp[j],dp[i]);
}
}
}
for(i = ; i <= o ; i++)
{
if(p[i].x<m&&p[i].y>m)
{
if(dp[m]>dp[p[i].x]+)
{
dp[m] = dp[p[i].x]+;
path[dp[m]] = i;
}
}
}
if(dp[m]==INF)
puts("No solution");
else
{
printf("%d\n",dp[m]);
for(i = ; i <= dp[m] ; i++)
printf("%d %d\n",p[path[i]].sx,p[path[i]].y);
}
return ;
}
1353. Milliard Vasya's Function
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
LL dp[][];
int main()
{
int i,j,g,s;
scanf("%d",&s);
for(int p = ; p <= ; p++)
dp[][p] = ;
LL ans=dp[][s];
for(i = ; i <= ; i++)
{
memset(dp,,sizeof(dp));
for(int p = ; p <= ; p++)
dp[][p] = ;
for(int o = ; o <= i ; o++)
for(j = ; j <= s ; j++)
{
if(o==)
{
dp[o][j]+=dp[o-][j-];
continue;
}
for(g = ; g <= ; g++)
{
if(g>j)
continue;
dp[o][j] += dp[o-][j-g];
}
}
ans+=dp[i][s];
}
if(s==)
ans++;
printf("%lld\n",ans);
return ;
}
1586. Threeprime Numbers
这题。。初始化数组里面一个顺序写反了 纠结了半天 三维保存两位的状态
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define LL long long
#define mod 1000000009
LL dp[][][];
int p[];
void init()
{
int i,j,x=;
for(i = ; i < ; i++)
{
for(j = ;j < i ; j++)
if(i%j==)
break;
if(j==i)
{
p[i] = ;
}
}
}
int main()
{
int i,j,n,o,g;
init();
scanf("%d",&n);
for(i = ; i <= ; i++)
{
if(p[i])
{
dp[][(i/)%][i/]++;
}
}
for(i = ; i <= n ;i++)
{
for(j = ; j <= ; j++)
{
for(g = ; g <= ; g++)
{
for(o = ; o <= ; o++)
{
int x1 = j*+g*+o;
if(p[x1])
{
dp[i][g][j] = (dp[i][g][j]+dp[i-][o][g])%mod;
}
}
}
}
}
LL ans=;
for(j = ; j <= ; j++)
for(i = ; i <= ; i++)
{
ans = (ans+dp[n][i][j])%mod;
}
printf("%lld\n",ans);
return ;
}