題目鏈接

題意

一共有T種螞蟻編號(hào)從1 到 T，給出A個(gè)螞蟻序列，問任取n個(gè)螞蟻一共可以組幾種集合，求S到B的種類和

AC

• dp
  狀態(tài)轉(zhuǎn)移方程為：
  
  K表示當(dāng)前螞蟻的數(shù)目

#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <map> #include <bitset> #include <string.h> #include <cmath> #include <algorithm> #define N 100015 #define P pair<int,int> #define ll long long #define mk(a, b) make_pair(a, b) #define mem(a, b) memset(a, b, sizeof(a)) using namespace std; int dp[N]; int inf = 0x3f3f3f3f; int mod = 1e6; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifint t, a, s, b;scanf("%d%d%d%d", &t, &a, &s, &b);// 記錄不同螞蟻的數(shù)目vector<int> v(t + 1);for (int i = 0; i < a; ++i) {int x;scanf("%d", &x);v[x]++;}// 記錄到第i個(gè)螞蟻，螞蟻的總數(shù)vector <int> sum(t + 1);for (int i = 1; i <= t; ++i) {sum[i] = sum[i - 1] + v[i];}mem(dp, 0);// 將一個(gè)螞蟻?zhàn)鳛檫吔?/span>for (int i = 0; i <= v[1]; ++i) {dp[i] = 1;}// 計(jì)算剩余螞蟻for (int k = 2; k <= t; ++k) {for (int i = b; i >= 1; --i) {// 當(dāng)前螞蟻數(shù)目超過總螞蟻數(shù)目，跳過循環(huán)if (i > sum[k]) continue;ll tot = 0;for (int j = 0; j <= v[k]; ++j) {if (i - j < 0) break;tot += dp[i - j];tot %= mod;}dp[i] = tot;}}ll ans = 0;for(int i = s; i <= b; ++i) {ans += dp[i];ans %= mod;}printf("%lld\n", ans);// cout <<ans <<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 3046 Ant Counting的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。