首页 > 代码库 > TYVJ1233

TYVJ1233

2024-07-19 11:56:36   221人阅读

这个题也不错。。
设dp[i][j](j<=i)表示前i个数删除j个时能留在自己位置的最大
数量
dp目标dp[n][i]中的最大值
决策：对于每个i有两种情况
1、删除 dp[i-1][j-1]
2、不删除{
又可分对立的两种
1) a[i]在自己的位置上 dp[i-1][j]+1
2) a[i]不在自己的位置上dp[i-1][j]
}

方程：
如果a[i]在自己的位置上
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]+1)
不在
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j])

初始化：

dp[i][i]=0;
因为状态转移的上一层需要事先得到i-1和j-1 则先初始化i==0
时，这时只有j=0需要赋值为0.
另外就是需要初始 前i个删除0个的时候，只要o(n)扫一遍就得
到

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6  7 const int maxn  = 1001; 8 int a[maxn],dp[maxn][maxn]; 9 int main()10 {11    // freopen("in.txt","r",stdin);12     int n;13     cin>>n;14     for(int i = 1;i<=n;++i)cin>>a[i];15     dp[0][0] = 0;16     for(int i = 1;i<=n;++i)17         for(int j = 1;j<i;++j)18         {19             int t = dp[i-1][j-1];20             if(a[i]==i-j)t = max(t,dp[i-1][j]+1);21             else t = max(t,dp[i-1][j]);22             dp[i][j] = t;23         }24     int ans = -1;25     for(int i = 0;i<=n;++i)26         ans = max(ans,dp[n][i]);27     printf("%d\n",ans);28     return 0;29 }

 

TYVJ1233


联系
我们