那一天我们许下约定
内部题，题干不粘了。
$30分算法$
首先看数据范围，可以写出来一个普通dp
#include<bits/stdc++.h> #define ll int #define A 2100 #define mod 998244353 using namespace std; ll f[1501][A+A+A],n,d,m; int main() { scanf("%d%d%d",&n,&d,&m); while(n!=0&&d!=0&&m!=0){ memset(f,0,sizeof(f)); f[0][0]=1; for(ll i=1;i<=d;i++) f[0][i]=1; for(ll i=1;i<=n;i++) for(ll k=1;k<=d;k++) { for(ll j=min(m-1,i);j>=0;j--) if(i-j>=0) f[i][k]=(f[i][k]+f[i-j][k-1])%mod; } printf("%d ",f[n][d]); scanf("%d%d%d",&n,&d,&m); } }
d最大为$1e^12$所以你这个dp会完美T掉或者M掉
$100分算法$
观察，发现n的范围非常小，m的范围也特别小。
所以我们利用这条性质，先片面的忽视掉这一天不给她饼干的情况，我们设定$f$定义为每天都给她饼干的情况。
设$f[i][j]$中i表示为前$i$天目前给了$j$个饼干的情况
然后可以推出来方程式
可以给她1～m-1个饼干
$f[i][j]=sum_limits {k=(j-M-1)}^{k<=j-1} f[i-1][k]$
然后直接转移，复杂度仍然难以接受，观察dp式子发现它是由一个字段转移过来的，我们要用前缀和维护优化一下。
仍然AC不了？
可能你会乘爆long long
注意多取模
#include<bits/stdc++.h> #define ll long long #define A 2010 #define mod 998244353 using namespace std; ll f[A][A],n,m,q,d; ll sum[A]; ll meng(ll x,ll k) { ll ans=1; for(;k;k>>=1,x=x*x%mod) if(k&1) ans=x*ans%mod; return ans%mod; } int main(){ while(1){ scanf("%lld%lld%lld",&n,&d,&m); ll ans=0; if(n==0&&d==0&&m==0){ return 0; } memset(f[1],0,sizeof(f[1])); f[0][0]=1; for(ll i=1;i<=min(n,m-1);i++) f[1][i]=1; for(ll i=2;i<=n;i++){ for(ll j=0;j<=n;j++) sum[j]=(sum[j-1]%mod+f[i-1][j]%mod)%mod; for(ll j=1;j<=n;j++) f[i][j]=(sum[j-1]%mod-sum[max(j-m,0ll)]%mod+mod)%mod; } ll sd=d%mod; for(ll i=1;i<=min(n,d);i++) { if(i==1) ans=(ans+sd*f[i][n]%mod)%mod,ans%=mod; else{ sd=(sd%mod*meng(i,mod-2)%mod*((d-i+1)%mod))%mod; ans%=mod; ans=(ans+f[i][n]%mod*sd%mod)%mod; } // if(sd!=0)printf("sd=%lld ans=%lld f*s=%lld ",sd,ans,f[i][n]*sd%mod); } cout<<(ans+mod)%mod<<endl; } }
那一天她离我而去
听说暴力可以AC所以我打的A*？？？
看不懂题解，如果给一个菊花图题解不就爆炸了吗？$2^{10000}$我觉得会炸
所以这个题瞎搞就行了？？？
然后我就瞎搞了个A*
跑的还特别快。大约600毫。
思路大约就是把每个直接与1相连的点拿出来，然后对于每个点跑A*，因为已经提前处理出来各种dis所以比较快。
然后没了
#include<bits/stdc++.h> using namespace std; #define ll int #define A 100010 #define in inline ll n,m; bool flag[A],ok=0; ll head[A],nxt[A],ver[A],tot1=0,t; ll head2[A],nxt2[A],ver2[A],cnt=0,tot2=0; ll value[A],value2[A],e,d[A],len=0; struct qnode{ ll v,w,sz,id; friend bool operator < (qnode x,qnode y) { return x.w+d[x.v]>y.w+d[y.v]; } }; void re() { tot1=1,tot2=1; memset(flag,0,sizeof(flag)); memset(head,0,sizeof(head));memset(head2,0,sizeof(head2)); memset(ver,0,sizeof(ver));memset(ver2,0,sizeof(ver2)); memset(nxt,0,sizeof(nxt));memset(nxt2,0,sizeof(nxt2)); memset(value,0,sizeof(value));memset(value2,0,sizeof(value2)); } in void add1(ll u,ll v,ll w) { ver[++tot1]=v; nxt[tot1]=head[u]; value[tot1]=w; head[u]=tot1; } in void add2(ll x,ll y,ll w) { ver2[++tot2]=y; nxt2[tot2]=head2[x]; value2[tot2]=w; head2[x]=tot2; } in void spfa(ll root) { memset(flag,0,sizeof(flag)); memset(d,0x3f,sizeof(d)); queue <ll>q; q.push(root); flag[root]=1; d[root]=0; while(!q.empty()) { ll x=q.front(); q.pop(); flag[x]=0; for(ll i=head[x];i;i=nxt[i]) { ll y=ver[i],w=value[i]; if(d[y]>d[x]+w) { d[y]=d[x]+w; if(!flag[y]) { flag[y]=1; q.push(y); } } } } return ; } in ll read() { ll x=0,f=1;char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*f; } in ll astar() { // 从每个直接相连的点开始跑A* ll ans=0x7ffffff; for(ll i=head[1];i;i=nxt[i]) { ll y=ver[i]; priority_queue<qnode> h; memset(flag,0,sizeof(flag)); qnode s; s.v=y,s.w=value[i],s.id=0; h.push(s); bool ok=0; while(!h.empty()) { qnode no=h.top(); // printf("当前 %d sumvalue=%d ",no.v,no.w); if(no.v==1){ ans=min(no.w,ans); break; } h.pop(); flag[no.v]=1; for(ll i=head2[no.v];i;i=nxt2[i]){ ll tu=ver2[i]; // printf("tu=%d ",tu); if(tu==1&&!ok){ ok=1; // printf("tu=%d ",tu); continue; } if(flag[tu]) {/*printf("掠过 ");*/continue;} // printf("没有掠过 "); qnode t; t.v=tu;t.w=value[i]+no.w;t.sz=no.sz+1; h.push(t); // printf("推入 %d->%d z=%d ",no.v,tu,value2[i]+no.w); } } } return ans; } int main() { scanf("%d",&t); while(t--) { re(); ll xx,yy;ll zz; n=read(),m=read(); for(ll i=1;i<=m;i++) { xx=read(),yy=read();zz=read(); add1(yy,xx,zz); add1(xx,yy,zz); add2(xx,yy,zz); add2(yy,xx,zz); } spfa(1); /* for(ll i=2;i<=tot1;i++){ printf("%d ",ver[i]); } for(ll i=1;i<=n;i++){ printf("%d ",d[i]); } */ ok=1; ll ans=astar(); if(ans>=1000000) cout<<-1<<endl; else printf("%d ",ans); } }