2024.2.28

**************************************************************************************************************

題目鏈接：P1002 [NOIP2002 普及組] 過河卒 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

?思路：用dfs其實也可以寫，不過這道題目會超時。由于題目上說只能往右邊還有下面走，所以每一點的條數(shù)是其左邊的條數(shù)加上右邊的條數(shù)，關(guān)系式為f(x,y)=f(x-1,y)+f(x,y-1);

具體方法注釋在代碼上了：

#include<bits/stdc++.h>
using namespace std;
int x,y,n,m;//(x,y)為b點坐標(biāo)，（n,m)為馬的坐標(biāo)
int p[30][30]={0};
long long f[30][30]={0};

int tx[9]={0,2,2,1,1,-1,-1,-2,-2};//馬的八種走法加上本來處于的那個點
int ty[9]={0,1,-1,2,-2,2,-2,1,-1};

int main()
{
    //輸入
    scanf("%d%d%d%d",&x,&y,&n,&m);
    x+=2;//防止越界，直接從2開始
    y+=2;
    n+=2;
    m+=2;
 
    //馬對應(yīng)的特殊點進(jìn)行賦值,賦為一，表示不可走
    for(int i=0;i<9;i++)
    {
        int mx=n+tx[i];
        int my=m+ty[i];
        p[mx][my]=1;
    }
    //由于每個點是左邊的條數(shù)加右邊的條數(shù)，起始點也如此，
    //所以在起始點的左邊或者上方任意一點賦為1即可
    f[2][1]=1;
    //遞推的計算f(x,y)
    for(int i=2;i<=x;i++)
    {
        for(int j=2;j<=y;j++)
        {
            if(p[i][j]==1)
            {
                f[i][j]=0;
                continue;
            }
            f[i][j]=f[i-1][j]+f[i][j-1];
        }
    }
    //輸出
    printf("%lld\n",f[x][y]);
    return 0;
}

**************************************************************************************************************

題目鏈接：P1216 [USACO1.5] [IOI1994]數(shù)字三角形 Number Triangles - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

思路：從上往下太復(fù)雜，直接從下往上看，上面一排的分別加上下面對應(yīng)的兩個數(shù)，哪個大哪個就更新哪個值，以此類推

看代碼：

#include<bits/stdc++.h>
using namespace std;
//為了簡單，從下往上看，倒數(shù)第二排的第一位數(shù)分別加倒數(shù)第一排的第一位數(shù)和第二位，
//哪個大就更新哪個值

int arr[1005][1005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&arr[i][j]);
        }
    }
    for(int i=n-1;i>0;i--)
    {
        for(int j=1;j<=i;j++)
        {
            arr[i][j]=max(arr[i+1][j]+arr[i][j],arr[i+1][j+1]+arr[i][j]);
        }
    }
    printf("%d\n",arr[1][1]);
    return 0;
}

**************************************************************************************************************

2.29?

題目：?P1802 5 倍經(jīng)驗日 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

思路：如下圖，一個一個填上去會知道一整個流程是什么，分兩種情況，一種是比對手多，則可以選擇贏和不贏，比較贏和不贏那個大取哪個值，若比對手少只能輸，則加上輸?shù)慕?jīng)驗，并且每一個前面的都是算好的其最大的，所以不用去加很多層的了，直接去加一個就好了，就如if? esle里面的語句

這里有很好的講解：【五倍經(jīng)驗日【洛谷P1802】-嗶哩嗶哩】 https://b23.tv/wRz7wkX

#include<cstdio>
#include<iostream>
using namespace std;

long long a[1005][2];//代表輸贏，【0】輸，【1】
long long b[1005];  //用來儲存至少使用的藥數(shù)量
long long f[1005];   //獲得的經(jīng)驗

int main()
{
    int n,x;
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&a[i][0],&a[i][1],&b[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=x;j>=0;j--)
        {
            if(j>=b[i])
            {
                f[j]=max(f[j]+a[i][0],f[j-b[i]]+a[i][1]);
            }
            else
            {
                f[j]+=a[i][0];
            }
        }
    }
    printf("%lld\n",5*f[x]);
    return 0;
}

**************************************************************************************************************

題目：P1616 瘋狂的采藥 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

思路：用dp，用兩個一維數(shù)組將數(shù)據(jù)分別存起來，然后dp【】里面的是時間，dp的值是最大價值，比較不采的與采藥的價值取最大值，其中采藥時的時間要花費了所以才會減去tim【i】

#include<bits/stdc++.h>
using namespace std;

long long tim[10005];//用來儲存時間
long long v[10005];//用來儲存價值
long long dp[10000005];//儲存最大價值，注意！要用long long 
int main()
{
    int t,m;
    scanf("%d%d",&t,&m);//時間和草藥數(shù)目
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&tim[i],&v[i]);
    }
    for(int i=1;i<=m;i++)//草藥數(shù)目
    {
        for(int j=tim[i];j<=t;j++)
        {
            dp[j]=max(dp[j],dp[j-tim[i]]+v[i]);
        }
    }
    printf("%lld",dp[t]);
    return 0;
}

**************************************************************************************************************

題目：P1439 【模板】最長公共子序列 - 洛谷 | 計算機科學(xué)教育新生態(tài) (luogu.com.cn)

最長公共子序列:不要求元素之間連續(xù)

思路：【樸素法】

定義一個二維數(shù)組dp【i】【j】以【0，i-1】number1的長度，和以【0，j-1】長度的number2兩串最長公共子序列

if(number1[i-1]==number2[j-1])

{d[i][j]=dp[i-1][j-1]+1;}

dp[i][j-1]【意思比如abc與ace少考慮e】? ??dp[i]-1[j]【意思比如abc與ace少考慮c】

把dp[i][0]和dp[0][j]初始化為0其他誰便初始化為啥都行，因為都會被覆蓋

for(int i=1;i<=number1.size;i++)

for(int j=1;j<=number2.size;j++)

最終結(jié)果為：dp[number1.size（）][number2.size()]; i

這是代碼：顯然是不適合這題的，需要進(jìn)行優(yōu)化

#include<bits/stdc++.h>
using namespace std;

int n1[100005];
int n2[100005];
int dp[10005][10005];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&n1[i]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&n2[i]);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(n1[i]==n2[j])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    printf("%d\n",dp[n][n]);
    return 0;
}

?優(yōu)化后用一維數(shù)組，否則數(shù)據(jù)太多已經(jīng)超出外面所承受的二維數(shù)組范圍了

【暫時還沒有會優(yōu)化后的方法，等會了再補上，先交一下總結(jié)吧】文章來源地址http://www.zghlxwxcb.cn/news/detail-839852.html

到了這里，關(guān)于動態(tài)規(guī)劃。第十三次的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！