杭电1087，，dp问题，求解答！

Question

#include
using namespace std;
int n;
int a[10005];
int vis[10005];

int dp(int n)
{
if(vis[n]!=-1)
return vis[n];
vis[n] = 0;
int i;
for(i= n-1;i>=0;i--)
{
if(i==-1)
return 0;

    dp(i);
    if(vis[i]>=vis[n])
        vis[n] = vis[i];

    if(a[i]<a[n])
    {

        int t = 0;;
        t += vis[i]+a[n];
        if(t>vis[n])
            vis[n] = t;
    }
}

}

int main()
{
while(1)
{
memset(a,0,sizeof(a));
memset(vis,-1,sizeof(vis));
cin>>n;

    if(n==0)
        break;
    else
    {
        int i;
        for(i = 1;i<=n;i++)
        {
            cin>>a[i];
        }
        dp(n);
    }

    cout<<vis[n]<<endl;
}
return 0;

}

不知道wa在哪里啊、、、、

Answer 1

该回答引用ChatGPT

这个程序可能存在以下几个问题：

• 未对 dp 函数进行返回值的设置
  在 dp 函数中，没有对返回值进行设置，应该在函数最后添加 return vis[n]; 来返回 vis[n] 的值。

• 没有对边界条件进行判断
  在 dp 函数中，当 i==-1 时，应该返回 0。否则，程序会进入死循环。

• 未考虑初始化条件
  在 dp 函数中，应该将 vis[n] 初始化为 a[n]。

• 下标从 1 开始
  在 main 函数中，数组 a 的下标从 1 开始，因此在输入时应该从 i = 1 开始循环。

下面是修改后的程序：

#include<iostream>
#include<cstring>
using namespace std;
int n;
int a[10005];
int vis[10005];

int dp(int n)
{
    if(vis[n]!=-1)
        return vis[n];
    vis[n] = a[n]; // 初始化 vis[n]
    int i;
    for(i= n-1;i>=0;i--)
    {
        if(i==-1)
            return 0;
        dp(i);
        if(vis[i]>=vis[n])
            vis[n] = vis[i];
        if(a[i]<a[n])
        {
            int t = 0;;
            t += vis[i]+a[n];
            if(t>vis[n])
                vis[n] = t;
        }
    }
    return vis[n]; // 返回 vis[n]
}

int main()
{
    while(1)
    {
        memset(a,0,sizeof(a));
        memset(vis,-1,sizeof(vis));
        cin>>n;
        if(n==0)
            break;
        else
        {
            int i;
            for(i = 1;i<=n;i++) // 数组下标从 1 开始
            {
                cin>>a[i];
            }
            dp(n);
        }
        cout<<vis[n]<<endl;
    }
    return 0;
}