POH! Lite C模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。

C: paiza事務局作成コード Vol.2 動的計画法

得点:100点
通過テストケース:7/7

#include <stdio.h>

int main()
{
    int m;int n;
    int ans;
    int sum_q;int sum_r;
    char str[128];
    int qr[50][2];
    int dp[210210];

    scanf("%d%d",&m,&n);
    sum_q = 0;
    sum_r = 0;
    for (int i = 0; i < n; i++){
        scanf("%d%d", &qr[i][0], &qr[i][1]);
        sum_q+=qr[i][0];
        sum_r+=qr[i][1];
    }

    int dp_m = sum_q - m;
    for (int i = 0; i < n; i++){
        int q = qr[i][0];
        int r = qr[i][1];
        for (int j = dp_m; j >= q; j--){
            dp[j] =(dp[j]>=dp[j-q]+r?dp[j]:dp[j-q]+r);
        }
    }

    sprintf(str,"%d",sum_r- dp[dp_m]);
    printf("%s\n",str);
}

C: paiza事務局作成コード Vol.1 O(2^n)

得点:71点
通過テストケース:5/7

#include <stdio.h>

int main(){
  int m;int n;
    int ans;
  char str[128];
  int qr[10][2];
  int use_list[1<<10][10];

  scanf("%d%d",&m,&n);
  for (int i = 0; i < n; i++){
    scanf("%d%d", &qr[i][0], &qr[i][1]);
  }

  //m社のうちi番目の会社を使うか使わないかの表を作る
  //3社とかなら
  // A, B, C
  // 1, 1, 1
  // 1, 1, 0
  // 1, 0, 1
  //.....続く...
  //みたいな1を使う0は使わないの表を作る


  //2進数で考えると
  for (int i = 0; i < (1<<n); i++){
    for(int j=0;j<n;j++){
      use_list[i][j] = (i>>j&1);
    }
  }

  //使う使わないリストから、人月を満たせる組み合わせで最安を探す
  ans = 0;
  for (int i = 0; i < n; i++)
  {
    ans += qr[i][1];
  }
  for (int i = 0; i < (1<<n); i++)
  {
    int cost = 0;
    int ningetsu = 0;
    for (int j = 0; j <n; j++)
    {
      if (use_list[i][j] == 1)
      {
        ningetsu += qr[j][0];
        cost += qr[j][1];
      }
    }
    if (ningetsu >= m && ans > cost)
    {
      ans = cost;
    }
  }


  sprintf(str,"%d",ans);
  printf("%s\n",str);

}
ページの先頭へ戻る