【#247_DIV2】-A B C

本文主要是介绍【#247_DIV2】-A B C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/contest/431

解题报告：

A - Black Square

一道神经病的题。。不知道为何水到如此地步。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn =1e5+50;char str[maxn];
int a[10];int main()
{cin>>a[1]>>a[2]>>a[3]>>a[4];scanf("%s",str);int i,ans=0;for(i=0;i<strlen(str);i++)  ans+= a[str[i]-'0'];cout<<ans<<endl;return 0;
}

B -  Shower Line

直接DFS搜出所有排列，找最大值即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;int g[6][6],que[6],vis[6];
int ans;int cal()
{return g[que[0]][que[1]]+g[que[1]][que[0]] + g[que[2]][que[3]]+g[que[3]][que[2]] + g[que[1]][que[2]]+g[que[2]][que[1]]+ g[que[3]][que[4]]+g[que[4]][que[3]] + g[que[2]][que[3]]+g[que[3]][que[2]] + g[que[3]][que[4]]+g[que[4]][que[3]];
}void dfs(int dep)
{int i;if(dep==5){int tans = cal();ans = max(ans,tans);//for(i=0;i<5;i++)cout<<que[i]<<" "; cout<<endl;return ;}for(i=0;i<5;i++){if(!vis[i]){vis[i] = 1;que[dep] = i;dfs(dep+1);vis[i] = 0;}}
}int main()
{freopen("input.txt","r",stdin);memset(g,0,sizeof(g));memset(vis,0,sizeof(vis));int i,j;for(i=0;i<5;i++)for(j=0;j<5;j++) cin>>g[i][j];ans=0;dfs(0);cout<<ans<<endl;return 0;
}

C -  k-Tree

一道DP题，没做出来。

以后切记！不会的题大胆猜DP！

dp[ n ][ 0 ] 表示权值和为 n 且路径中没有 >= d 的边的最多路径数。

dp[ n ][ 1 ] 表示权值和为 n 且路径中有 >= d 的边的最多路径数。

输入 n ,k ,d 之后，先把能一步到的 n 给赋上值。

dp[ 1~(d-1) ][ 0 ] = 1

dp[ d~k ][ 1 ] = 1

接下来，多于一步的路径由以下公式推出：

dp[ i ][ 0 ] = dp[ i -1 ][ 0 ] + dp[ i -2 ][ 0 ] + .... + dp[ i - d + 1 ][ 0 ]

dp[ i ][ 1 ] = dp[ i -1 ][ 1 ] + dp[ i -2 ][ 1 ] + .... + dp[ i - k ][ 1 ] + dp[ i -d ][ 0 ] + dp[ i - d - 1 ][ 0 ] + .... + dp[ i - k ][ 0 ]

然后每一步都要取模，取模。。取模。。。。真是烦啊，像我代码里那样就行了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;int mol(int x){return x%MOD;
}int dp[120][2];int main()
{//freopen("input.txt","r",stdin);memset(dp,0,sizeof(dp));int n,k,d,i,j;cin>>n>>k>>d;for(i=1;i<d;i++) dp[i][0]=1;for(i=d;i<=k;i++) dp[i][1]=1;for(i=1;i<=n;i++){for(j=i-1; j>=0 && j>=i-d+1; j--) {dp[i][0] = mol(mol(dp[i][0]) + mol(dp[j][0]));}for(j=i-1; j>=0 && j>=i-k; j--) {dp[i][1] = mol(mol(dp[i][1]) + mol(dp[j][1]));}for(j=i-d; j>=0 && j>=i-k; j--) {dp[i][1] = mol(mol(dp[i][1]) + mol(dp[j][0]));}//cout<<i<<": "<<dp[i][0]<<" "<<dp[i][1]<<endl;}cout<<dp[n][1]<<endl;return 0;
}

这篇关于【#247_DIV2】-A B C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---