DP基礎吧。A掉還是挺爽的。就是考慮在兩端只能是從前一秒的內部一米或原來的點來進行，但是在5秒以內可到達點是逐漸外擴的，并不是[0,10]，所以就特殊考慮了一下。后面兩端是0和10，中間的點可以從上一秒的左邊/本身/右邊過來，保證每次最優這樣下來就好了。

#include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <algorithm> using namespace std; #define LL long long #define INF 0x3f3f3f3f const double pi = acos(-1.0);const int mod =9973;const int N = 1e5+10;int n; int dp[5][20]; int a[N][20];int main() {int k,x,y,T;while(~scanf("%d",&n)&&n){memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));T=0;for(int i=0;i<n;i++){scanf("%d%d",&x,&y);a[y][x]++; T=max(T,y);}/*for(int i=1;i<=T;i++){for(int j=0;j<=10;j++)printf("%d ",a[i][j]);puts("");}puts("");*/k=0;dp[k][4]=a[1][4];dp[k][5]=a[1][5];dp[k][6]=a[1][6];/* for(int i=0;i<=10;i++)printf("%d ",dp[k][i]);puts("");*/if(T<=5){for(int i=2;i<=T;i++){k=1-k;for(int j=(5-i);j<=(5+i);j++){if(j==(5-i))dp[k][j]=a[i][j]+dp[1-k][j+1];else if(j==(5+i))dp[k][j]=a[i][j]+dp[1-k][j-1];elsedp[k][j]=max(dp[1-k][j],max(dp[1-k][j+1],dp[1-k][j-1]))+a[i][j];}}int ans=0;for(int i=0;i<=10;i++)ans=max(ans,dp[k][i]);printf("%d\n",ans);continue;}for(int i=2;i<=5;i++){k=1-k;for(int j=(5-i);j<=(5+i);j++){if(j==(5-i))dp[k][j]=a[i][j]+dp[1-k][j+1];else if(j==(5+i))dp[k][j]=a[i][j]+dp[1-k][j-1];elsedp[k][j]=max(dp[1-k][j],max(dp[1-k][j+1],dp[1-k][j-1]))+a[i][j];}}for(int i=6;i<=T;i++){k=1-k;for(int j=0;j<=10;j++){if(j==0)dp[k][j]=a[i][j]+max(dp[1-k][j],dp[1-k][j+1]);else if(j==10)dp[k][j]=a[i][j]+max(dp[1-k][j],dp[1-k][j-1]);elsedp[k][j]=max(dp[1-k][j],max(dp[1-k][j+1],dp[1-k][j-1]))+a[i][j];}}int ans=0;for(int i=0;i<=10;i++)ans=max(ans,dp[k][i]);printf("%d\n",ans);}return 0; }

后來我又寫了一發發現其實沒有必要考慮前五秒的路線，反正我前一狀態沒有走過就是0，那么就算本來前五秒過程中走不到的地方，我也當成走到了，反正前一狀態就是0；

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <algorithm> #include <math.h> #include <queue> #include <stack> #include <map> using namespace std; #define INF 0x3f3f3f3f #define pi acos(-1.0) #define MAX 100010 #define mod 9973 #define LL long longconst int N=1e5+10;int a[N][20]; int dp[5][20];int main() {int n,x,y,k;while(~scanf("%d",&n)&&n){memset(a,0,sizeof(a));memset(dp,0,sizeof(dp));int T;T=0;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);a[y][x]++;T=max(T,y);}k=1;dp[k][5]=a[1][5];dp[k][4]=a[1][4];dp[k][6]=a[1][6];for(int i=2;i<=T;i++){k=1-k;for(int j=10;j>=0;j--){if(j==0){dp[k][j]=a[i][j]+max(dp[1-k][j+1],dp[1-k][j]);}else if(j==10){dp[k][j]=a[i][j]+max(dp[1-k][j-1],dp[1-k][j]);}elsedp[k][j]=a[i][j]+max(dp[1-k][j-1],max(dp[1-k][j+1],dp[1-k][j]));}}int ans=dp[k][0];for(int i=0;i<=10;i++){ans=max(ans,dp[k][i]);}cout<<ans<<endl;} return 0; }

轉載于:https://www.cnblogs.com/keyboarder-zsq/p/5934477.html

總結

以上是生活随笔為你收集整理的hdoj1176【DP】的全部內容，希望文章能夠幫你解決所遇到的問題。

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