http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1223
#include <iostream>
using namespace std;
int money[8] = { 0, 1, 2, 5, 10, 20, 50, 100 };
long int dp[8][251];
int main()
{
int i, j, n;
for (i = 0; i < 8; i++)
{
dp[i][0] = 1;
dp[i][1] = 1;
}
for (i = 0; i < 251; i++)
{
dp[0][i] = 1;
dp[1][i] = 1;
}
for (i = 2; i < 8; i++)
{
for (j = 2; j < 251; j++)
{
if (j - money[i] >= 0)
{
dp[i][j] = dp[i][j-money[i]] + dp[i-1][j];
}
else
{
dp[i][j] = dp[i-1][j];
}
}
}
while (cin >> n && n != 0)
{
cout << dp[7][n] << endl;
}
}
找零钱= =
dynamic programming= =
最后还是用一下代码打表了，经由贺贺优化的= =
#include <iostream>
#include <cstdio>
using namespace std;
long int count(int n)
{
long int sum = 0;
int i, j, k, p, q, r, s;
for (i = 0; i <= n/100; i++)
for (j = 0; j <= n/50; j++)
for (k = 0; k <= n/20; k++)
for (p = 0; p <= n/10; p++)
for (q = 0; q <= n/5; q++)
for (r = 0; r <= n/2; r++)
// for (s = n; s >=0; s--)
{
int t =100*i+50*j+20*k+10*p+5*q+2*r;
if (t<=n && n-t+i+j+k+p+q+r<=100)//&& t >= 0)//其实可以去掉=1的情况，减少无用循环
{
//printf("100:%d 50:%d 20:%d 10:%d 5:%d 2:%d 1:%d\n",i,j,k,p,q,r,s);
sum++;
}
}
return sum;
}
int main()
{
freopen("d:\\liyiningweisuo.txt","w",stdout);
int n=1;
while (n<251)
{
cout<<"case "<<n<<": cout<<""<<count(n)<<""<<endl;break;"<<endl;
n++;
//cout<<n<<endl;
}
return 0;
}
以下是比赛时提交的代码= =
#include "iostream"
using namespace std;
int main()
{
int n;
while(cin>>n)
{
switch(n)
{
case 1:
cout<<"1"<<endl;
break;
case 2:
cout<<"2"<<endl;
break;
case 3:
cout<<"2"<<endl;
break;
case 4:
cout<<"3"<<endl;
break;
case 5:
cout<<"4"<<endl;
break;
case 6:
cout<<"5"<<endl;
break;
case 7:
cout<<"6"<<endl;
break;
case 8:
cout<<"7"<<endl;
break;
case 9:
cout<<"8"<<endl;
break;
case 10:
cout<<"11"<<endl;
break;
case 11:
cout<<"12"<<endl;
break;
case 12:
cout<<"15"<<endl;
break;
case 13:
cout<<"16"<<endl;
break;
case 14:
cout<<"19"<<endl;
break;
case 15:
cout<<"22"<<endl;
break;
case 16:
cout<<"25"<<endl;
break;
case 17:
cout<<"28"<<endl;
break;
case 18:
cout<<"31"<<endl;
break;
case 19:
cout<<"34"<<endl;
break;
case 20:
cout<<"41"<<endl;
break;
case 21:
cout<<"44"<<endl;
break;
case 22:
cout<<"51"<<endl;
break;
case 23:
cout<<"54"<<endl;
break;
case 24:
cout<<"61"<<endl;
break;
case 25:
cout<<"68"<<endl;
break;
case 26:
cout<<"75"<<endl;
break;
case 27:
cout<<"82"<<endl;
break;
case 28:
cout<<"89"<<endl;
break;
case 29:
cout<<"96"<<endl;
break;
case 30:
cout<<"109"<<endl;
break;
case 31:
cout<<"116"<<endl;
break;
case 32:
cout<<"129"<<endl;
break;
case 33:
cout<<"136"<<endl;
break;
case 34:
cout<<"149"<<endl;
break;
case 35:
cout<<"162"<<endl;
break;
case 36:
cout<<"175"<<endl;
break;
case 37:
cout<<"188"<<endl;
break;
case 38:
cout<<"201"<<endl;
break;
case 39:
cout<<"214"<<endl;
break;
case 40:
cout<<"236"<<endl;
break;
case 41:
cout<<"249"<<endl;
break;
case 42:
cout<<"271"<<endl;
break;
case 43:
cout<<"284"<<endl;
break;
case 44:
cout<<"306"<<endl;
break;
case 45:
cout<<"328"<<endl;
break;
case 46:
cout<<"350"<<endl;
break;
case 47:
cout<<"372"<<endl;
break;
case 48:
cout<<"394"<<endl;
break;
case 49:
cout<<"416"<<endl;
break;
case 50:
cout<<"451"<<endl;
break;
case 51:
cout<<"473"<<endl;
break;
case 52:
cout<<"508"<<endl;
break;
case 53:
cout<<"530"<<endl;
break;
case 54:
cout<<"565"<<endl;
break;
case 55:
cout<<"600"<<endl;
break;
case 56:
cout<<"635"<<endl;
break;
case 57:
cout<<"670"<<endl;
break;
case 58:
cout<<"705"<<endl;
break;
case 59:
cout<<"740"<<endl;
break;
case 60:
cout<<"793"<<endl;
break;
case 61:
cout<<"828"<<endl;
break;
case 62:
cout<<"881"<<endl;
break;
case 63:
cout<<"916"<<endl;
break;
case 64:
cout<<"969"<<endl;
break;
case 65:
cout<<"1022"<<endl;
break;
case 66:
cout<<"1075"<<endl;
break;
case 67:
cout<<"1128"<<endl;
break;
case 68:
cout<<"1181"<<endl;
break;
case 69:
cout<<"1234"<<endl;
break;
case 70:
cout<<"1311"<<endl;
break;
case 71:
cout<<"1364"<<endl;
break;
case 72:
cout<<"1441"<<endl;
break;
case 73:
cout<<"1494"<<endl;
break;
case 74:
cout<<"1571"<<endl;
break;
case 75:
cout<<"1648"<<endl;
break;
case 76:
cout<<"1725"<<endl;
break;
case 77:
cout<<"1802"<<endl;
break;
case 78:
cout<<"1879"<<endl;
break;
case 79:
cout<<"1956"<<endl;
break;
case 80:
cout<<"2064"<<endl;
break;
case 81:
cout<<"2141"<<endl;
break;
case 82:
cout<<"2249"<<endl;
break;
case 83:
cout<<"2326"<<endl;
break;
case 84:
cout<<"2434"<<endl;
break;
case 85:
cout<<"2542"<<endl;
break;
case 86:
cout<<"2650"<<endl;
break;
case 87:
cout<<"2758"<<endl;
break;
case 88:
cout<<"2866"<<endl;
break;
case 89:
cout<<"2974"<<endl;
break;
case 90:
cout<<"3121"<<endl;
break;
case 91:
cout<<"3229"<<endl;
break;
case 92:
cout<<"3376"<<endl;
break;
case 93:
cout<<"3484"<<endl;
break;
case 94:
cout<<"3631"<<endl;
break;
case 95:
cout<<"3778"<<endl;
break;
case 96:
cout<<"3925"<<endl;
break;
case 97:
cout<<"4072"<<endl;
break;
case 98:
cout<<"4219"<<endl;
break;
case 99:
cout<<"4366"<<endl;
break;
case 100:
cout<<"4563"<<endl;
break;
case 101:
cout<<"4709"<<endl;
break;
case 102:
cout<<"4905"<<endl;
break;
case 103:
cout<<"5051"<<endl;
break;
case 104:
cout<<"5247"<<endl;
break;
case 105:
cout<<"5442"<<endl;
break;
case 106:
cout<<"5637"<<endl;
break;
case 107:
cout<<"5832"<<endl;
break;
case 108:
cout<<"6027"<<endl;
break;
case 109:
cout<<"6221"<<endl;
break;
case 110:
cout<<"6476"<<endl;
break;
case 111:
cout<<"6669"<<endl;
break;
case 112:
cout<<"6924"<<endl;
break;
case 113:
cout<<"7116"<<endl;
break;
case 114:
cout<<"7369"<<endl;
break;
case 115:
cout<<"7622"<<endl;
break;
case 116:
cout<<"7875"<<endl;
break;
case 117:
cout<<"8127"<<endl;
break;
case 118:
cout<<"8378"<<endl;
break;
case 119:
cout<<"8628"<<endl;
break;
case 120:
cout<<"8954"<<endl;
break;
case 121:
cout<<"9202"<<endl;
break;
case 122:
cout<<"9526"<<endl;
break;
case 123:
cout<<"9772"<<endl;
break;
case 124:
cout<<"10094"<<endl;
break;
case 125:
cout<<"10415"<<endl;
break;
case 126:
cout<<"10735"<<endl;
break;
case 127:
cout<<"11054"<<endl;
break;
case 128:
cout<<"11371"<<endl;
break;
case 129:
cout<<"11686"<<endl;
break;
case 130:
cout<<"12093"<<endl;
break;
case 131:
cout<<"12406"<<endl;
break;
case 132:
cout<<"12810"<<endl;
break;
case 133:
cout<<"13119"<<endl;
break;
case 134:
cout<<"13520"<<endl;
break;
case 135:
cout<<"13920"<<endl;
break;
case 136:
cout<<"14318"<<endl;
break;
case 137:
cout<<"14713"<<endl;
break;
case 138:
cout<<"15106"<<endl;
break;
case 139:
cout<<"15497"<<endl;
break;
case 140:
cout<<"15998"<<endl;
break;
case 141:
cout<<"16384"<<endl;
break;
case 142:
cout<<"16880"<<endl;
break;
case 143:
cout<<"17262"<<endl;
break;
case 144:
cout<<"17754"<<endl;
break;
case 145:
cout<<"18243"<<endl;
break;
case 146:
cout<<"18729"<<endl;
break;
case 147:
cout<<"19212"<<endl;
break;
case 148:
cout<<"19692"<<endl;
break;
case 149:
cout<<"20169"<<endl;
break;
case 150:
cout<<"20776"<<endl;
break;
case 151:
cout<<"21246"<<endl;
break;
case 152:
cout<<"21847"<<endl;
break;
case 153:
cout<<"22311"<<endl;
break;
case 154:
cout<<"22905"<<endl;
break;
case 155:
cout<<"23495"<<endl;
break;
case 156:
cout<<"24081"<<endl;
break;
case 157:
cout<<"24663"<<endl;
break;
case 158:
cout<<"25240"<<endl;
break;
case 159:
cout<<"25812"<<endl;
break;
case 160:
cout<<"26539"<<endl;
break;
case 161:
cout<<"27103"<<endl;
break;
case 162:
cout<<"27821"<<endl;
break;
case 163:
cout<<"28375"<<endl;
break;
case 164:
cout<<"29083"<<endl;
break;
case 165:
cout<<"29786"<<endl;
break;
case 166:
cout<<"30483"<<endl;
break;
case 167:
cout<<"31174"<<endl;
break;
case 168:
cout<<"31859"<<endl;
break;
case 169:
cout<<"32538"<<endl;
break;
case 170:
cout<<"33398"<<endl;
break;
case 171:
cout<<"34065"<<endl;
break;
case 172:
cout<<"34913"<<endl;
break;
case 173:
cout<<"35567"<<endl;
break;
case 174:
cout<<"36401"<<endl;
break;
case 175:
cout<<"37228"<<endl;
break;
case 176:
cout<<"38048"<<endl;
break;
case 177:
cout<<"38859"<<endl;
break;
case 178:
cout<<"39662"<<endl;
break;
case 179:
cout<<"40458"<<endl;
break;
case 180:
cout<<"41465"<<endl;
break;
case 181:
cout<<"42245"<<endl;
break;
case 182:
cout<<"43234"<<endl;
break;
case 183:
cout<<"43997"<<endl;
break;
case 184:
cout<<"44970"<<endl;
break;
case 185:
cout<<"45933"<<endl;
break;
case 186:
cout<<"46885"<<endl;
break;
case 187:
cout<<"47828"<<endl;
break;
case 188:
cout<<"48762"<<endl;
break;
case 189:
cout<<"49686"<<endl;
break;
case 190:
cout<<"50851"<<endl;
break;
case 191:
cout<<"51754"<<endl;
break;
case 192:
cout<<"52899"<<endl;
break;
case 193:
cout<<"53781"<<endl;
break;
case 194:
cout<<"54903"<<endl;
break;
case 195:
cout<<"56013"<<endl;
break;
case 196:
cout<<"57111"<<endl;
break;
case 197:
cout<<"58197"<<endl;
break;
case 198:
cout<<"59271"<<endl;
break;
case 199:
cout<<"60332"<<endl;
break;
case 200:
cout<<"61671"<<endl;
break;
case 201:
cout<<"62705"<<endl;
break;
case 202:
cout<<"64018"<<endl;
break;
case 203:
cout<<"65026"<<endl;
break;
case 204:
cout<<"66309"<<endl;
break;
case 205:
cout<<"67578"<<endl;
break;
case 206:
cout<<"68833"<<endl;
break;
case 207:
cout<<"70073"<<endl;
break;
case 208:
cout<<"71296"<<endl;
break;
case 209:
cout<<"72503"<<endl;
break;
case 210:
cout<<"74029"<<endl;
break;
case 211:
cout<<"75206"<<endl;
break;
case 212:
cout<<"76699"<<endl;
break;
case 213:
cout<<"77839"<<endl;
break;
case 214:
cout<<"79297"<<endl;
break;
case 215:
cout<<"80738"<<endl;
break;
case 216:
cout<<"82159"<<endl;
break;
case 217:
cout<<"83562"<<endl;
break;
case 218:
cout<<"84944"<<endl;
break;
case 219:
cout<<"86308"<<endl;
break;
case 220:
cout<<"88035"<<endl;
break;
case 221:
cout<<"89360"<<endl;
break;
case 222:
cout<<"91045"<<endl;
break;
case 223:
cout<<"92327"<<endl;
break;
case 224:
cout<<"93970"<<endl;
break;
case 225:
cout<<"95593"<<endl;
break;
case 226:
cout<<"97191"<<endl;
break;
case 227:
cout<<"98768"<<endl;
break;
case 228:
cout<<"100318"<<endl;
break;
case 229:
cout<<"101850"<<endl;
break;
case 230:
cout<<"103791"<<endl;
break;
case 231:
cout<<"105272"<<endl;
break;
case 232:
cout<<"107162"<<endl;
break;
case 233:
cout<<"108595"<<endl;
break;
case 234:
cout<<"110434"<<endl;
break;
case 235:
cout<<"112250"<<endl;
break;
case 236:
cout<<"114034"<<endl;
break;
case 237:
cout<<"115795"<<endl;
break;
case 238:
cout<<"117525"<<endl;
break;
case 239:
cout<<"119231"<<endl;
break;
case 240:
cout<<"121396"<<endl;
break;
case 241:
cout<<"123044"<<endl;
break;
case 242:
cout<<"125152"<<endl;
break;
case 243:
cout<<"126740"<<endl;
break;
case 244:
cout<<"128786"<<endl;
break;
case 245:
cout<<"130806"<<endl;
break;
case 246:
cout<<"132787"<<endl;
break;
case 247:
cout<<"134743"<<endl;
break;
case 248:
cout<<"136660"<<endl;
break;
case 249:
cout<<"138547"<<endl;
break;
case 250:
cout<<"140953"<<endl;
break;
}
}
}
知道什么叫无节操无下限么，这就是LIN同学想出的方法= =
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2072
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char a[110];
int n;
while(cin>>a>>n)
{
while(n>0)
{
int i=0;
while(i<strlen(a)&&a[i]<=a[i+1])
{
i++;
}
while(i<=strlen(a))
{
a[i]=a[i+1];
i++;
}
n--;
}
while(a[0]=='0'&&a[1]!='\0')
{
int i=0;
while(i<strlen(a))
{
a[i]=a[i+1];
i++;
}
}
cout<<a<<endl;
}
}
删数字，注意80056 1，这种数字，删除前导零！
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2073
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct example
{
int elem1;
int elem2;
} example;
bool comparison(example a,example b)
{
return a.elem2<b.elem2;
}
int main()
{
int count=0;
int n;
while(cin>>n)
{
vector<example> array(n);
for(int i=0; i<n; i++)
{
cin>>array[i].elem1>>array[i].elem2;
}
sort(array.begin(),array.end(),comparison);
count=0;
int timestart=0;
for(int i=0; i<=n-1; i++)
{
if(array[i].elem1>=timestart)
{
count++;
timestart=array[i].elem2;
}
}
cout<<count<<endl;
}
}
以上代码可以作为结构体排序的模板，换一下elem1或者elem2就可以对两个关键字进行排序，结合strcmp即可对字符串进行全排序（即对所有字符进行排序，“SAB”与“SBA”虽然ASCII码都一样，但是仍然输出前面小于后面）。而且，vector库里面的数组大小是可以动态申请的= =。。
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef struct
{
int elem1;
int elem2;
}example;
bool comparison(example a,example b)
{
return a.elem1<b.elem1;
}
int main()
{
int n;int i=0;
while(cin>>n)
{
int money,kind;
double weight=0.00;
cin>>money>>kind;
vector <example> a(n);
for(int i=0;i<kind;i++)
{
cin>>a[i].elem1>>a[i].elem2;
}
sort(a.begin(),a.end(),comparison);
while(1)
{
if(money>(a[i].elem1)*(a[i].elem2))
{
money-=a[i].elem1*a[i].elem2;
weight+=1.0*(a[i++].elem2);
}
else
{
weight+=1.0*money/a[i].elem1;
break;
}
}
cout<<fixed<<setprecision(2)<<weight<<endl;
}
}