「FJ互测」「BZOJ3704」昊昊的机油之GRST
题目描述(grst.c/cpp/pas)
昊昊有个好机油，他就是传说中的着力点。现在昊昊获得了一份长度为n的GRST牌（mod 4 意义下），打算作为送给好机油的生日礼物（不是在2月的么）。但是，昊昊深知他的机油是个神犇，作为数字控的他，只会喜欢特定的序列。但是昊昊不怕，他可以使用一次菲亚特（他的机油最喜欢的大招），将一段区间内的数字全部+1，若某个数字为3，则+1后变为0。但昊昊的神力是有限的，问从初始序列a到达最终序列b，最少需要使用多少次菲亚特。
输入格式(grst.in)
从stdin读入
第一行一个正整数n，表示GRST长度。
接下来两行，每行n个值，分别表示ai bi。
输出格式(grst.out)
从stdout读入
仅一个数，即最少需要使用多少次菲亚特。
样例输入
3
0 2 1
1 0 2
样例输出
2
数据规模与约定
样例说明：第一次对区间[1,2] 使用菲亚特。第二次对区间[2,3] 使用菲亚特。
| 测试点编号 | N |
| 1 | 5 |
| 2 | 10 |
| 3 | 100 |
| 4 | 1000 |
| 5 | 10000 |
| 6 | 100000 |
| 7 | 1000000 |
| 8 | 1000000 |
| 9 | 10000000 |
| 10 | 10000000 |
0<=ai,bi<=3
时间限制
1s
内存限制
1G
题解
记录 f[i][j]为做到第 i 位的高度为 j 的最小代价，dp60-80分
|
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 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define ll long long #define inf 0x7fffffff using namespace std; inline ll read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,a[1000005],b[1000005],c[1000005]; int f[1000005][10]; int ans; int main() { //freopen("grst.in","r",stdin); //freopen("grst.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); for(int i=1;i<=n;i++) { c[i]=b[i]-a[i]; if(c[i]<0)c[i]+=4; } memset(f,127/3,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++) for(int x=0;x<=9;x++) for(int y=0;y<=9;y++) { int a=c[i-1]+x*4,b=c[i]+y*4; f[i][y]=min(f[i][y],f[i-1][x]+max(0,b-a)); } ans=inf; for(int i=0;i<=9;i++) ans=min(ans,f[n][i]); printf("%d",ans); return 0; } |
先考虑构造合法解,每次都对一个后缀加上一定的值。
对于合法解的优化,我们可以在差分序列上选择一位进行-4 操 作,相当于对后缀-4,可以节省的代价根据(当前位-上一位)决定。
所以,我们先对于差分序列中为 3 的位置考虑-4,可以节省 3 的 代价。
剩下的依次贪心,注意判断序列合法性
|
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 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,ans,tot; int a[10000005],b[10000005],c[10000005]; int d[10000005],f[10000005]; int main() { n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)b[i]=read(); for(int i=1;i<=n;i++) { c[i]=b[i]-a[i]; if(c[i]<c[i-1])c[i]+=(c[i-1]-c[i])/4*4; if(c[i]<c[i-1])c[i]+=4; f[i]=c[i]/4; d[i]=c[i]-c[i-1]; } ans=c[n];f[n+1]=inf; tot=0; for(int i=1;i<=n;i++) if(d[i]==3&&f[i]>tot){d[i]-=4;ans-=3;tot++;} for(int i=1;i<=n;i++)c[i]=c[i-1]+d[i]; for(int i=n;i;i--)f[i]=min(c[i]/4,f[i+1]); tot=0; for(int i=1;i<=n;i++) if(d[i]==2&&f[i]>tot){d[i]-=4;ans-=2;tot++;} for(int i=1;i<=n;i++)c[i]=c[i-1]+d[i]; for(int i=n;i;i--)f[i]=min(c[i]/4,f[i+1]); tot=0; for(int i=n;i;i--) if(d[i]==1&&f[i]>tot){d[i]-=4;ans--;tot++;} printf("%d",ans); return 0; } |
Subscribe
计数器 9854657
OI 课件=>
OI 课件=>