首页 > 代码库 > TYVJ1246

TYVJ1246

2024-07-19 06:44:11   217人阅读

存在性DP
没多少好说的
bool dp[i][j] 表示跳到第i个格子能不能得到j的得分
对于每一个格子，枚举可以跳到这个格子的其他的格子，在从这些格子中选出其可以跳到的分数，将其反应到i中即dp[i][k] = true 最后遍历dp[n][m-1 -> 0]找出值为true的最大j值即是ans 这题目有坑，就是没个格子的分数Dx可能很大，在T*Dx时可能超int所以要先把Dx mod m在乘

 

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

 

TYVJ1246


联系
我们