桂林電子科学技術大学第3回ACMプログラム設計コンテスト部分題解(i,j,c)

i題リンク:https://ac.nowcoder.com/acm/contest/558/I出典:牛客網
子猫が序列を研究している.子猫は選択を研究している.長さNのシーケンスa 1,a 2,...,aNを与えて、このNの要素の中からいくつか(選択しなくてもよい、選択しなくてもよい)を選んでください.任意の1≦iの典型的なdp問題に対する制限の条件は、選択時に隣接する2つの数を選択できないことです.dp【i】を現在のi番目のシーケンス列の最大値とすると、a[i]に対して2つの状態選択または選択しないことになります.
dp[i]=max(dp[i-2]+a[i],dp[i-1])/選んだらdp[i-2]しか継承できない、選ばないならdp[i-1]
コードは以下の通りです.

#include

using namespace std;
const int maxn = 200;
int dp[maxn];
int a[maxn];

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i = 0; i < n; i++)
        {
            cin>>a[i];
        }
        dp[0] = a[0];
        dp[1] = max(a[0],a[1]);//       
        for(int i = 2; i < n; i++)
        {
            dp[i] = max(dp[i-2]+a[i],dp[i-1]);
        }
        cout<

j題リンク:https://ac.nowcoder.com/acm/contest/558/J出典:牛客網
子猫がグリッド図を研究しています.子猫は連通性を研究している.Nを1枚与える×Mのグリッド図は、文字0と1しか含まれていません.1で形成されたインターフェースブロックはいくつありますか.2つの1は連通しており、そのうちの1つが別の上、下、左、右の4つの方向の1つに位置し、1つの点bfsに対してこの点が1であれば、その点bfsに隣接する点に対して再アクセスがマークされている場合、1とマークされている点が他の連通ブロックで異なる場合、アクセスコードは以下の通りである.

#include//                   

using namespace std;
const int maxn = 100;

int n,m;
int x[4] = {0,0,1,-1};
int y[4] = {1,-1,0,0};

char mp[maxn][maxn];
int vis[maxn][maxn];
void bfs(int x1,int y1)
{
    for(int i = 0; i < 4; i++)//     
    {
        if(x1+x[i]=0&&y1+y[i]=0&&vis[x1+x[i]][y1+y[i]]==0&&mp[x1+x[i]][y1+y[i]]=='1')
        {
            vis[x1+x[i]][y1+y[i]] = 1;
            //cout<>t;
    while(t--)
    {
        int sum = 0;
        cin>>n>>m;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                cin>>mp[i][j];
                vis[i][j] = 0;
            }
        }
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(mp[i][j]=='1'&&vis[i][j]==0)
                {
                    sum++;
                    bfs(i,j);
                }
            }
        }
        cout<

cリンク:https://ac.nowcoder.com/acm/contest/558/C出典:牛客網
子猫は二元グループを研究している.子猫は最大値を研究している.N個の二元群(a 1,b 1),(a 2,b 2),...,(aN,bN)を与えて、aiの最小値とbiの最小値の和が最大になるように適切なK個を選択してください.aiの最小値とbiの最小値の和を出力してくださいaに対して先にソートしてから優先キューの中の小根スタックメンテナンスbでk個の出入りキューごとに最小値をメンテナンスする最大値コードは以下の通りです.

#include//                     
#include
#include
using namespace std;
const int maxn = 100000+10;
typedef long long ll;
struct node{
    ll a;
    ll b;
}num[maxn];//   a  

bool cmp(node x, node y)
{
    return x.a>y.a;
}
priority_queue, greater > q;  //                      

int main()
{
    int n,k;
    cin>>n>>k;
    for(int i = 0; i < n; i++)
        cin>>num[i].a>>num[i].b;
    sort(num,num+n,cmp);
    for(int i = 0; i < k; i++)
    {
        q.push(num[i].b);
    }
    ll ans = num[k-1].a+q.top();
    for(int i = k; i < n; i++)
    {
        q.pop();
        q.push(num[i].b);
        if(num[i].a+q.top()>ans)//      i       b      a  b    
            ans = num[i].a+q.top();
    }
    cout<