n^2的dp可过第一问
第二问只要从左往右贪心的取数就好了 只要当前的数的f[i]>l-top 且大于前一个数 就可以取来
千万要注意 题目中说的字典序最小是下标字典序最小而不是序列的字典序最小!!!!!!!
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=10010; int f[N],s[N],n,m,q,ans[N],maxdp; void read(int &x){ char c; while((c=getchar())<'0' || c>'9');x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0'; } int main(){ //freopen("1046.in","r",stdin);freopen("1046.out","w",stdout); read(n); for(int i=1;i<=n;i++) read(s[i]);s[0]=~0u>>1; for(int i=n;i>=1;i--){ f[i]=1; for(int j=i+1;j<=n;j++) if(s[i]<s[j]) f[i]=max(f[i],f[j]+1); maxdp=max(maxdp,f[i]); } read(m); while(m--){ int l; read(l); if(maxdp>=l){ int top=0; ans[0]=-(~0u>>1); for(int i=1;i<=n;i++) if(l-f[i]<=top && s[i]>ans[top]) ans[++top]=s[i]; for(int i=1;i<l;i++) printf("%d ",ans[i]);printf("%d\n",ans[l]); } else printf("Impossible\n"); } return 0; }
推dp方程
首先将所有的工厂按距离排序
定义f[i]表示前i个工厂的所有货都能够保存下来的最小费用,cost[i][j]为把所有i到j的货物运到j的费用,那么显然
$f[i]=min{ f[j]+cost[j+1][i]+c[i]} (0\leq j \leq i-1)$
考虑如何计算cost[i][j],定义sum[i]表示前i个工厂的物品个数之和,d[i]表示工厂i到第一个工厂的距离 那么可以得到
$cost[i][j]=cost[1][j]-cost[1][i]-sum[j]*(d[j]-d[i])$
于是只要预处理出cost[1][i]和sum[i]就可以O(1)计算cost[i][j]。下面用cost[i]表示cost[1][i]
看到n这么大,我们试一试斜率优化
假设j>k,且决策j比k优
那么有
$f[j]+cost[i]-cost[j]-sum[j]*(d[i]-d[j])+c[i] < f[k]+cost[i]-cost[k]-sum[k]*(d[i]-d[k])+c[i]$
将所有有关i的移项到右边其他移到左边可以得到
$(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k] < d[i]*(sum[j]-sum[k])$
由于sum[j]>sum[k],可以除过来,否则要考虑不等号变向问题 则
$\frac{(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k]}{(sum[j]-sum[k])} < d[i]$ d[i]递增可以斜率优化
#include <cstdio> #include <algorithm> using namespace std; typedef long long LL; const int N=1000010; struct Fact{LL c,d,p;}fa[N]; LL n,cost[N],f[N],sum[N],q[N*3],l,r; bool cmp(Fact a,Fact b){return a.d<b.d;} double slop(int k,int j){return (f[j]-cost[j]-(f[k]-cost[k])+sum[j]*fa[j].d-sum[k]*fa[k].d)/(double)(sum[j]-sum[k]);} void read(LL &x){ char c; while((c=getchar())<'0' || c>'9');x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0'; } int main(){ //freopen("1096.in","r",stdin);freopen("1096.out","w",stdout); read(n); for(int i=1;i<=n;i++) read(fa[i].d),read(fa[i].p),read(fa[i].c); sort(fa+1,fa+n+1,cmp); for(int i=1;i<=n;i++) sum[i]=sum[i-1]+fa[i].p,cost[i]=cost[i-1]+sum[i-1]*(fa[i].d-fa[i-1].d); for(int i=1;i<=n;i++){ while(l<r && slop(q[l],q[l+1])<fa[i].d) l++; int j=q[l]; f[i]=f[j]+cost[i]-cost[j]-sum[j]*(fa[i].d-fa[j].d)+fa[i].c; while(l<r && slop(q[r-1],q[r])>slop(q[r],i)) r--; q[++r]=i; } printf("%lld",f[n]); return 0; }
看起来是个傻逼题
定义f[i][j]表示第i个节目音量能否为j ,则f[i][j]= f[i-1][j+c[i]] || f[i-1][j-c[i]]。最后扫一下f[n]里面的最大值
滚动数组都不用开就过了
代码
#include <cstdio> #include <algorithm> using namespace std; int n,bl,ml,a[55],ans=0; bool f[55][1010]; int main(){ // freopen("2748.in","r",stdin);freopen("2748.out","w",stdout); scanf("%d%d%d",&n,&bl,&ml); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[0][bl]=1; for(int i=1;i<=n;i++) for(int j=0;j<=ml;j++) { if(j-a[i]>=0 && f[i-1][j-a[i]]) f[i][j]=1; if(j+a[i]<=ml && f[i-1][j+a[i]]) f[i][j]=1; } for(int i=ml;i>=0;i--) if(f[n][i]) {printf("%d",i);ans=1;break;} if(!ans) printf("-1"); return 0; }
这题本来第一个反应是数位dp 然而看到n这么大- - 管他呢照样数位dp 矩阵快速幂优化一下就好了
这道题的关键 是 利用kmp算法 构建转移矩阵
定义f[i][j]表示 i位的数字的最后j位 和不吉利数字的开始j位相同 的方案数有多少,然后我们就开始想转移方程,然而 这转移不是和给出的数字串有关吗……(其实我本来以为是f[i][j]=f[i-1][j-1]+9*f[i-1][j+1]的,打好之后发现样例都过不去……) 。既然字符串给出了 那我们一定可以用奇技淫巧弄出转移的方程 ——对就是kmp
我们用kmp算法匹配的时候 是不断的用fail指针跳转 直到匹配成功为止 在这里我们用相同的方法处理
对于某一个匹配长度k,我们枚举这个位置的数字i 然后进行匹配 fail指针不断的回跳 直到匹配成功或者跳出了字符串 这时候 我们就知道 匹配长度为k的字符串 在添加一个数字i之后 可以转移到哪个位置,转移矩阵中的对应位置++即可。这样就构造成功了转移矩阵,接下来就是用矩阵快速幂随便搞一下,把f[n][0]到f[n][m-1]加起来模一下就是答案了
代码
#include <cstdio> #include <algorithm> using namespace std; int n,m,mod,s[30],f[30],nxt[30],sum; struct mat{ int a[30][30]; void reset(){for(int i=0;i<30;i++) for(int j=0;j<30;j++) a[i][j]=0;} void set1(){reset();for(int i=0;i<=29;i++) a[i][i]=1;} friend mat operator *(mat x,mat y){ mat z; z.reset(); for(int i=0;i<=20;i++) for(int j=0;j<=20;j++) for(int k=0;k<=20;k++) (z.a[i][j]+=x.a[i][k]*y.a[k][j])%=mod; return z; } }st,zy,ans; void get(){ int p; f[0]=0;f[1]=0; for(int i=2;i<=m;i++) { p=f[i-1]; while(s[p]!=s[i-1] && p) p=f[p]; f[i]= s[p]==s[i-1]?p+1:0; } for(int i=0;i<m;i++) for(int j=0;j<=9;j++) { if(j==s[i]) {zy.a[i][i+1]++;continue;} int p=f[i]; while(s[p]!=j && p) p=f[p]; if(s[p]==j) zy.a[i][p+1]++;else zy.a[i][0]++; } } int main(){ //freopen("1009.in","r",stdin);freopen("1009.out","w",stdout); scanf("%d%d%d\n",&n,&m,&mod); for(int i=0;i<m;i++) s[i]=getchar()-'0'; get(); ans.set1(); st.a[0][0]=1; for(;n;n>>=1){if(n&1)ans=ans*zy;zy=zy*zy;} st=st*ans; for(int i=0;i<m;i++) (sum+=st.a[0][i])%=mod; printf("%d",sum); return 0; }