那一天我們許下約定

內部題，題干不粘了。

$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\n",f[n][d]);scanf("%d%d%d",&n,&d,&m);} } View Code

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\n",sd,ans,f[i][n]*sd%mod); } cout<<(ans+mod)%mod<<endl;} } View Code

?

?那一天她離我而去

聽說暴力可以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\n",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\n",tu);if(tu==1&&!ok){ok=1; // printf("tu=%d \n",tu);continue;}if(flag[tu]){/*printf("掠過\n");*/continue;} // printf("沒有掠過\n"); qnode t;t.v=tu;t.w=value[i]+no.w;t.sz=no.sz+1;h.push(t); // printf("推入 %d->%d z=%d\n",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\n",ver[i]);}for(ll i=1;i<=n;i++){printf("%d\n",d[i]);} */ ok=1;ll ans=astar();if(ans>=1000000) cout<<-1<<endl;elseprintf("%d\n",ans);} } View Code

?

轉載于:https://www.cnblogs.com/znsbc-13/p/11218768.html

總結

以上是生活随笔為你收集整理的NOIP模拟测试6「那一天我们许下约定（背包dp）·那一天她离我而去」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。